转载

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

题目：

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

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

思路：参照Ｃ++ 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

正文到此结束