LeetCode/31. 下一个排列

31. 下一个排列

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

来源：力扣（LeetCode）
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解：

本题很绕，不好想。基本思路就是，由于我们我们要找到比当前结点大的最小排列，所以我们需要从后往前遍历，找到一对(i,j)，使(i,j)满足i<j。此时的i就是我们要交换的元素的位置；然后，我们在(j, nums.length)范围内，找到比num[i]大的最小数字nums[j]和nums[i]交换；交换完成后，我们还需要使(j,nums.length)保持最小，即升序排列，这样才能保证找到的是比原排列大的，最小的排列。

具体代码如下：

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums.length == 0 || nums.length == 1) return;
        if (nums.length == 2) {
            int temp = nums[0];
            nums[0] = nums[1];
            nums[1] = temp;
            return;
        }
        int len = nums.length - 2;
        //寻找第一个升序队
        while (len > -1 && nums[len + 1] <= nums[len]) {
            len--;
        }
        //如果不存在下一个更大的排列，则将数字重新排列成最小的排列
        if (len < 0) {
            Arrays.sort(nums);
            return;
        } else {
            int j = nums.length - 1;
            //找到需要交换的位置
            while (j >= 0 && nums[j] <= nums[len]) {
                j--;
            }
            int temp = nums[j];
            nums[j] = nums[len];
            nums[len] = temp;
            //交换后让后面升序，保证最小
            Arrays.sort(nums, len + 1, nums.length);
            return;
        }
    }
}