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, 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

Tips:

题意： 比如1，2，3，4，就是这四个数所有的permutations，按order排序，然后这个permutation在排序中的下一个。

O(n)

1. 在当前序列中，从尾端往前寻找两个相邻元素，前一个记为first，后一个记为second，并且满足first < second。
2. 然后再从尾端寻找另一个元素number，如果满足first 小于number，即将第first个元素与number元素对调.
3. 并将second元素之后（包括second）的所有元素颠倒排序，即求出下一个序列

example:

6，3，4，9，8，7，1

1. 此时 first ＝ 4，second = 9
2. 从尾巴到前找到第一个大于first的数字，就是7
3. 交换4和7，即上面的swap函数，此时序列变成6，3，7，9，8，4，1
4. 再将second＝9以及以后的序列重新排序，让其从小到大排序，使得整体最小，即reverse一下（因为此时肯定是递减序列）

得到最终的结果：6，3，7，1，4，8，9

1. Start from its last element, traverse backward to find the first one with index i that satisfy num[i-1] < num[i]. So, elements from num[i] to num[n-1] is reversely sorted.
2. To find the next permutation, we have to swap some numbers at different positions, to minimize the increased amount, we have to make the highest changed position as high as possible. Notice that index larger than or equal to i is not possible as num[i,n-1] is reversely sorted. So, we want to increase the number at index i-1, clearly, swap it with the smallest number between num[i,n-1] that is larger than num[i-1]. For example, original number is 121543321, we want to swap the '1' at position 2 with '2' at position 7.
3. The last step is to make the remaining higher position part as small as possible, we just have to reversely sort the num[i,n-1]

Code:

public class Solution {
    public void nextPermutation(int[] nums) {
        // find two adjacent elements, n[i-1] < n[i]
        int i = nums.length - 1;
        for (; i > 0; i --) {
            if (nums[i] > nums[i-1]) {
                break;
            }
        }
        if (i != 0) {
            // swap (i-1, x), where x is index of the smallest number in [i, n)
            int x = nums.length - 1;
            for (; x >= i; x --) {
                if (nums[x] > nums[i-1]) {
                    break;
                }
            }
            swap(nums, i - 1, x);
        }
        reverse(nums, i, nums.length - 1);
    }

    void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
    // reverse a[i, j]
    void reverse(int[] a, int i, int j) {
        for (; i < j; i ++, j --) {
            swap(a, i, j);
        }
    }
}