31. 下一个排列

题目

整数数组的一个排列就是将其所有成员以序列或线性顺序排列。

例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。
整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的 下一个排列 就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。
给你一个整数数组 nums ，找出 nums 的下一个排列。

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

思路

初看这道题，我陷入了一个错误的思路：当从 [1,2,3] 转移到 [1,3,2] 时，是因为 3 比 2 大，所以可以进行交换，同理，2 比 1 大，所以接下来会变换为 [2,1,3]，但是如果以交换的视角看待这个问题，不可避免地，会在发生进位时遇到各种变换上的问题，以使算法无法执行下去。

经过了一些思考，我在某次胡乱写画后，仿佛顿悟一般，突然想到，如果不以交换的视角，而以递增的视角看待这个问题，算法呼之欲出。

首先，算法从数组的末位开始向前循环执行，对每一项采取相同的策略进行判别，具体执行步骤为：

一个旧的方案，写着写着就发现有优化方案^_^!

复制一份数组，并按升序排序，作为 顺序数组，方便后续取比当前项更大的值的数组
（接下来的步骤均是对每一项进行判断，从数组的最末位开始。）取当前项之前的所有数字组成一个 不可变换集合，集合记录每一项数字出现的数量
接下来在 顺序数组 中找到比当前数字都大的所有数字组成一个 候选数组，表示当前项初步可以变换为的数字集
接下来从 候选数组 中剔除 不可变换集合 中的数字，每次剔除只剔除一个数字，并将 不可变换集合 中的对应项记录的数字减一，表示剔除一次。循环执行，直到 候选数组 中不再包含任何 不可变换集合 中的数字。
接下来取 候选数组 的第一位，记为 A
- 如果第一位为空，表示这一项无法递增，取前一项并返回第 2 步循环执行
- 如果不为空，则进行下一步
取当前项及之后的所有项，作为 重排序数组，并将上一步取出的数字 A 从这个数组中剔除一次
将当前项改为 A
将 重排序数组 按升序排序
将 重排序数组 替换当前项之后的所有项
最后做一下边界处理，当循环结束后，如果数组的索引为 -1，说明所有位均无法递增，也即，输入的数组为降序，按照题意，将数组直接执行一次升序排序即可

取当前项之后的所有项，作为 重排序数组
将 重排序数组 按升序排序
找到第一个大于当前项的数
- 若无法找到这样的数，则对前一项重新执行循环
- 若可以找到，则执行下一步
将当前项与找到的数对换一下
将当前项之后的所有项替换为 重排序数组 中对位的项，程序返回
最后做一下边界处理，当循环执行到结束时，说明所有位均无法递增，也即输入的数组为降序，按照题意，将数组直接反向即可

假设输入 [1,3,2,4,3]，对于最后一位 3 和下一位 4：

其重排序数组分别为 [] 和 [3]，均无法取出一个比其自身大的数，故循环会以前一项继续执行

对于前一位的 2 ：

其重排序数组为，

1	reOrderNums = [3,4] // [4,3] 升序排序一下

第一个比当前项大的数字为 3，则将当前项与该数字对换，此时，原数组和重排序数组分别为，

1 2	nums = [1,3,3,4,4] reOrderNums = [2,4]

最后将 reOrderNums 覆盖到原数组结尾，得到 [1,3,3,2,4]，完成递增。

可以发现，最后一位的重排序数组一定为空，故循环可以从倒数第二位开始。

需要注意的是：因为题目说明需要原地修改，因而所有的变更最终都需要直接操作传入的数组本身，重新赋值是无效的。

解

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  let pt = nums.length - 2; // 从倒数第二位开始
  while (pt >= 0) {
    // 取当前项的后面所有项，做升序重排序
    const reOrderNums = nums.slice(pt + 1);
    reOrderNums.sort((a, b) => a - b);

    // 找出第一个大于当前项的数字
    const firstLargerItemIndex = reOrderNums.findIndex(
      (item) => item > nums[pt]
    );

    if (firstLargerItemIndex < 0) { // 如果找不到，则重新对前一项做循环
      pt--;
      continue;
    } else {
      // 交换当前项和找到的项
      const tmp = nums[pt];
      nums[pt] = reOrderNums[firstLargerItemIndex];
      reOrderNums[firstLargerItemIndex] = tmp;
      // 将重排序数组覆盖到原数组末尾
      nums.splice(pt + 1, reOrderNums.length, ...reOrderNums);
      return;
    }
  }
  // 执行至此表示所有数均无法递增，即 nums 为降序数组，将原数组直接反向即可
  nums.reverse();
};