31. Next Permutation

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

难度:medium

题目:

实现下一个排列数,将数字按词法顺序重新排列为下一个更大的数字置换。如果这样的排序不存在,它一定轮转到了最小的那个数。

必须原地置换并且只允许使用常量空间

思路:参照C++ STL库中实现的next_permutation

Runtime: 8 ms, faster than 98.59% of Java online submissions for Next Permutation.

Memory Usage: 31.2 MB, less than 0.97% of Java online submissions for Next Permutation.

class Solution {
    /**
    * 1. find i <  j (i + 1) from end to start
    * 2. find i < k swap (i, k) from end to start
    * 3. reverse [j, last]
    */
    public void nextPermutation(int[] nums) {
        if (null == nums || nums.length <= 1) {
            return;
        }
        
        int right = nums.length - 1;
        int j = right;
        for (; j > 0; j--){
            if (nums[j - 1] < nums[j]) break;
        }
        for (int k = right; k >= 0; k--) {
            if (j > 0 && nums[k] > nums[j - 1]) {
                swapArray(nums, j - 1, k);
                break;
            }
        }

        for (; j < right; j++, right--) {
            swapArray(nums, j, right);
        }
    }
    
    private void swapArray(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

原文 

https://segmentfault.com/a/1190000018116768

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » 31. Next Permutation

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址