[LeetCode 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

Solution

E.g 1,2,6,4,2 ===> next permutation: 1,4,2,2,6

1. 首先求出第一个需要更换的数：从数组尾部开始向前扫描，第一个比前一个数小的那个数。此例中就是index==1的2.
2. 求出第二个需要更换的数： 找出比1中求出的数要大，但又是最接近它的那个数，此例中为4：
   • 分析可知，从replaceIndex以后的数就是降序，所以只需找到从replaceIndex - end这个范围内，最小的且比replace number大的数即可。
3. 交换1和2中求出的数： 1，4，6，2，2
4. 因为求的是next permutation，所以把replaceIndex + 1， end这个subarray按升序排序以后，就得到结果1,4,2,2,6

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length < 2) {
            return;
        }
        
        // 1. find the first number which is smaller from the end
        // that is the one need to replace
        // eg. 1,2,6,4,2; replace number is 2 (index = 1)   ===> final result: 1,4,2,2,6
        int replaceIndex = nums.length - 2;
        while (replaceIndex >= 0) {
            if (nums[replaceIndex] < nums[replaceIndex + 1]) {
                break;
            }
            replaceIndex --;
        }
        
        // 6,5,4,3,2,1
        if (replaceIndex < 0) {
            Arrays.sort (nums);
            return;
        }
        
        // eg. 1,2,6,4,2
        // 2. find another number which is larger than the replaced one but is cloest number as well
        // in the example, the replaceIndex = 1, value is 2; the closest larger one is 4
        // from the replaceIndex + 1, we already know they in are decending order, 
        // therefore just need to find the smallest one (largere than replaceIndex number of course)
        int anotherReplaceIndex = replaceIndex + 1;
        while (anotherReplaceIndex < nums.length && nums[anotherReplaceIndex] > nums[replaceIndex]) {
            anotherReplaceIndex ++;
        }
        
        //3. swap
        int temp = nums[anotherReplaceIndex - 1];
        nums[anotherReplaceIndex - 1] = nums [replaceIndex];
        nums [replaceIndex] = temp;
        
        //4. sort the subarray after replace Index
        Arrays.sort (nums, replaceIndex + 1, nums.length);
        
    }
}