31. 下一个排列

一、题目描述

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

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

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

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 100

二、解题思路

2.1 个人想法

我自己的想法是，既然是下一个比它大的排序值，那肯定是改变值的位置越靠后越好。

比如 123，改变2的值变成132，肯定比改变1的值变成213更贴近原值。

• 首先就是要找到最靠后的可以交换的值

什么样的值是可以改变的？

• 既然是求下一个大值，那么这个改变值的后续序列中，肯定要有比改变值大的

比如 42531，改变值就是2，因为531的后面都没有比它们大的值，而2的后续值53比2大，这个时候改变2的值，就能获取比它更大的值。

后续序列中比改变值大的可能有多个，那应该改变哪个值呢？

• 既然是下一个大值，那肯定是改变的越小越好

比如前面的 42531，2换成3的改变是最小的，因为3比2大，并且2和3最接近。

交换之后就可以了吗？

实际还不行，交换后的值为 43521，但是可以发现，43125 < 43521

• 所以除了交换值以外，还需要对后续的序列进行升序排序

总的步骤可以分为3步：

1. 找到要改变的值，它的后续值中有比它大的值，比如前面说的2；
2. 找到后续值中比它大的最小值，作为改变值即将交换的值，比如前面说的2和3；
3. 对后续的序列进行升序排序。

2.2 官方解法

官方的思路其实和我的差不多，但是比我的更精妙，时间复杂度也比我的低得多。

1. 第一步，也是找出改变值，但是它不像我那样遍历寻找，而是倒序找到第一个逆序元素，也就是满足 nums[i] < nums[i + 1]，num[i] 就是需要改变的值。为什么这样做？其实看前面的例子 42531，确实可以发现，2是满足 nums[i] < nums[i + 1]，不得不说，官方的这个想法比我好多了~~

2. 第二步，找出需要交换的值，也就是比改变值大的最小值。官方的更直接，前面第一步找的就是第一个逆序元素，也就意味着，改变值之后的序列，是一个降序序列，从我前面的例子可以看出，2的后续序列531确实是降序的，所以只要从后往前找到第一个比2大的值，就是要最小的比2大的值，也就是3。

3. 第三步，排序，因为前面知道了改变值的后续序列是降序的，而且交换之后，实际上也是降序的，如交换后43521，521依旧是降序的。所以只要把降序的521倒过来变成125，就是升序了，无需做排序操作（官方牛逼~~）

总之，虽然思路是差不多的，但是官方的精妙得多，时间复杂度比我低了整整一个等级~~~~

三复杂度分析

1）个人解法

• 时间 O(n^2)
• 空间 O(1)

2）官方解法

• 时间 O(n)
• 空间 O(1)

四、参考代码

1）个人代码

/**
 * 31. 下一个排列
 * @param nums 数组
 */
private void nextPermutation(int[] nums) {
    for (int i = nums.length - 2; i >= 0; i--) {
        int index = findMinMax(nums, nums[i], i + 1, nums.length);
        if (index > -1) {
            int temp = nums[i];
            nums[i] = nums[index];
            nums[index] = temp;
            Arrays.sort(nums, i + 1, nums.length);
            return;
        }
    }
    Arrays.sort(nums);
}

/**
 * 查找比k大的最小值的索引
 * @param nums 数组
 * @param k 指定值
 * @param start 起始索引
 * @param end 结束索引
 * @return 索引，或-1
 */
private int findMinMax(int[] nums, int k, int start, int end) {
    int maxIndex = -1;
    for (int i = start; i < end; i++) {
        if (nums[i] <= k) {
            continue;
        }
        if (maxIndex == -1 || nums[maxIndex] > nums[i]) {
            maxIndex = i;
        }
    }
    return maxIndex;
}

2）官方代码

/**
 * 31. 下一个排列
 * @param nums 数组
 */
private void nextPermutation(int[] nums) {
    // 寻找第一个逆序值
    int index = nums.length - 2;
    while (index >= 0 && nums[index] >= nums[index + 1]) {
        index--;
    }
    // 交换比逆序值大的最小值
    for (int i = nums.length - 1; index >= 0 && i > index; i--) {
        if (nums[i] > nums[index]) {
            int temp = nums[i];
            nums[i] = nums[index];
            nums[index] = temp;
            break;
        }
    }
    // 后面这部分是降序的，倒过来转成升序
    int lp = index + 1, rp = nums.length - 1;
    while (lp < rp) {
        int temp = nums[lp];
        nums[lp++] = nums[rp];
        nums[rp--] = temp;
    }
}