题目链接

mplement 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, do not allocate 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

乍一看没啥头绪 - - ，于是参考了 C++ 的 std::next_permutation() 的实现和这个问题下排名第一的仁兄的答案。

1 2 3 4 5
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
…

观察发现，假设某个元素的 index 为 k，当 nums[k, …, nums.length - 1] 不递增时，nums[k - 1] 需要改变为一个更大的数，即改变为 nums[k, …, nums.length - 1] 中恰大于 nums[k - 1] 的数。交换这两个数，并 reverse nums[k, …, nums.length - 1]。注意判重就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
public class Solution {
    public void nextPermutation(int[] nums) {
        if(nums.length == 0) return; // no such cases
        int len = nums.length;
        int k = len - 1;
        // everything to the right of nums[k - 1] is in nonincreasing order
        while(k > 0 && nums[k] <= nums[k - 1]) // avoid duplication
            k--;
        if(k == 0)
            reverse(nums, 0, len - 1);
        else {
            int i = 0;
            // find the number just larger than nums[k - 1]
            for(i = len - 1; ; i--) {
                if(nums[i] > nums[k - 1])
                    break;
            }
            // then swap them
            swap(nums, k - 1, i);
            reverse(nums, k, len - 1);
        }
    }
    
    private void reverse(int[] nums, int l, int r) {
        while(l < r)
            swap(nums, l++, r--);
    }
    
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}