Leetcode 31.下一个排列

题目描述：

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

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

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

示例 1：

1
2

输入：nums = [1,2,3]
输出：[1,3,2]

示例 2：

1
2

输入：nums = [3,2,1]
输出：[1,2,3]

示例 3：

1
2

输入：nums = [1,1,5]
输出：[1,5,1]

示例 4：

1
2

输入：nums = [1]
输出：[1]

提示：

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

链接：

https://leetcode-cn.com/problems/next-permutation

题目分析

  首先我们要分析 “字典序” 中下一个排列是什么，下一个排列是比当前排列大的最小的排列。
  为了获取到比当前排列 “大” 的排列，则表明在从左往右数的某一位中，新排列的数字比原排列的大，而在此之前所有的数字均与原排列一样。由于越往右表示的权重越小，则为了使新排列尽可能的 “小”，我们应该令改变的数字尽可能地靠右。另一方面，改变的数字必须从原数字的右边选取，并且必须比原数字大。那么靠右的极限是什么？应该是后面的每个数的右边均不存在比自己小的数了，也即意味着，右边的数是降序排列（包含相同）的。我们只需要从数组最后往前找，找到第一个降序的数（不包含相同），这样就找到了需要换数字的某一位数（最右的降序排列反着找就是升序排列，而我们要找到第一个不符合的数），我们把这个下标记为 left。
  为了使新排列尽可能的小，我们需要换的数字也必须尽可能的小，因此我们需要在右边的降序排列中找到比 nums[left] 大，但是又尽可能地小的数。也即从数组最后往前找，找到第一个比 nums[left] 大的数（此时相当于是升序查找的，因此可以保证尽可能地小），我们把这个数记为 nums[right]。
  将 nums[right] 与 nums[left] 交换后，已经可以保证新排列比原排列大，为了使新排列尽可能地小，我们需要另 nums[left] 之后的序列变为升序序列，这样是最小的情况。而我们进行交换的时候，有 nums[right-1] >= nums[right] > nums[left] >= nums[right+1]，则可以保证将 nums[left] 交换到 nums[right] 原本的位置后，右边的降序序列仍然是降序序列，则使用一个 reverse 函数将这部分反转为升序序列即可。同时的，这个函数是由双指针实现的，可以保证题目要求的原地修改。

  对于题目中的边界情况有 ①原数组是降序排列（最大排列），这个时候寻找不到 nums[left]，也即寻找到的 left 值为 -1。而我们需要反转的区间原本应该是 left+1 ~ end，刚好 left 为 -1 时，反转区间从 0 开始，也即将整个数组进行反转，成为升序排列（最小排列），符合题意。②原数组只有一个数，这种情况其实等同于上一种情况，只是最大排列和最小排列是相同的，将其进行反转也不会改变什么，因此不需要进行单独处理。因此最后的代码如下。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int left = nums.size()-2;
        while(left >= 0 && nums[left] >= nums[left + 1]){
            left--;
        }
        if(left >= 0){
            int right = nums.size()-1;
            while(right > left && nums[right] <= nums[left]){
                right--;
            }
            swap(nums[left], nums[right]);
        }
        reverse(nums.begin()+left+1, nums.end());
    }
};

  时间复杂度：$O(n)$，其中 $n$ 为数组的长度。因为我们只进行了两次扫描，一次反转操作，这些操作的时间复杂度均为 $O(n)$。
  空间复杂度：$O(1)$。我们只需要两个变量存放交换的数字位置，一个变量用于数组反转。