31. Next Permutation

Leetcode link

解题思路

本题要求我们通过排列组合得出下一个更大的排列，以 [1,2,3] 为例子，这三个数字总共有 6 种可能的排列组合，从小到大依次是 [1,2,3] 、[1,3,2] 、[2,1,3] 、[2,3,1] 、[3,1,2] 、[3,2,1]，最后一个 [3,2,1] 按照题目的要求要返回 [1,2,3]

那么要怎么找到下一个更大的排列呢？我们以 [4,5,2,6,3,1] 为例：

1. 要找到下一个更大的，我们必须从右往左看，找到从右往左看第一个不是升序的元素，也就是 2

2. 然后我们再重新从右往左看，找到第一个大于 2 的元素，也就是 3

3. 我们把 2 跟 3 交换之后，得到 [4,5,3,6,2,1]，可以明显看出来现在已经比原来的大了，但是太大了

4. 我们发现，可以对第一个交换元素的后面进行排序来缩小这个数，也就是针对 [6,2,1] 排序

5. 最后我们得到 [4,5,3,1,2,6]

6. 最后我们可以推断出，步骤 4 要排序的序列一定是降序的，所以我们可以通过反转来进一步降低复杂度

C++

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

Javascript

Array.prototype.myReverse = function (start, end) {
    const arr = this;
    while (start < end) {
        [arr[start], arr[end]] = [arr[end], arr[start]];
        start++;
        end--;
    }
    return arr;
};

var nextPermutation = function (nums) {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }
    if (i >= 0) {
        let j = nums.length - 1;
        while (j >= 0 && nums[i] >= nums[j]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    i < 0 ? nums.reverse() : nums.myReverse(i + 1, nums.length - 1);
};