Next Permutation 52

Question

Given a list of integers, which denote a permutation.

Find the next permutation in ascending order.

Notice

The list may contains duplicate integers.

Example

For [1,3,2,3], the next permutation is [1,3,3,2]

For [4,3,2,1], the next permutation is [1,2,3,4]

Solution

下一个permutation就是使得整个数列增加的值最小的变化（除了当前数列为递减数列，则下一个permutation为递增数列）。为了使得下一个数列与当前数列相比增加值最小，则要使增加的位置越低位（越靠右）越好，同时增加增加的值越小越好，因此从后往前遍历每一位，寻找第一个比当前位小的数，找到一个最靠右的第一个小的数，如果有两个数的第一个小的数的位置相同，则选择较小的那个数（增加值小）。遍历完成后，将那个数和第一个小的数交换位置，同时对第一个原来第一个小的数的位置之后的所有数递增排序即可。如果遍历完成后没有找到第一个小的数，则说明当前数列递减，则对整个数列递增排序即可。

代码如下：

public class Solution {
    /**
     * @param nums: an array of integers
     * @return: return nothing (void), do not return anything, modify nums in-place instead
     */
    public int[] nextPermutation(int[] nums) {
        // write your code here
        if(nums == null || nums.length == 0){
            return nums;
        }

        int pos = -1;
        int index = -1;
        //从后往前寻找每位上的数遇到的第一个比自己小的数，记录下第一个小的数的位置以及当前数的值，选择位置最大（最靠右）的第一个大的数和最小的当前数（即增加值最小）
        for(int i = nums.length - 1; i > 0; i--){
            if(i <= pos){
                break;
            }

            for(int j = i - 1; j >= 0; j--){
                if(nums[i] > nums[j]){
                    if(pos > j){
                        break;
                    }else if(pos == j && nums[i] >= nums[index]){
                        break;
                    }else{
                        pos = j;
                        index = i;
                    }
                }
            }
        }
        //说明当前数组减，则next permutation为递增数组，对整个数组排序即可
        if(pos == -1){
            Arrays.sort(nums);
            int i = 0;
            //防止出现0开头的情况
            while(i < nums.length && nums[i] == 0){
                i++;
            }
            int temp = nums[0];
            nums[0] = nums[i];
            nums[i] = temp;
        }else{
            //交换两个数，同时对改变值的位置之后的所有数排序
            int temp = nums[pos];
            nums[pos] = nums[index];
            nums[index] = temp;
            Arrays.sort(nums, pos + 1, nums.length);
        }
        return nums;
    }
}