Skip to main content

下一个排列

题目​

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

例如, 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.length <= 100
  • 0 <= nums[i] <= 100
示例
输入: nums = [1, 2, 3]
输出: [1, 3, 2]
输入: nums = [3, 2, 1]
输出: [1, 2, 3]
输入: nums = [1, 1, 5]
输出: [1, 5, 1]

题解​

这道题的目的是寻找下一个比它大的最近接的那个值, 我们用 13481 这个数字来演示:

  • 首先从十位看起, 也就是 81, 它已经是十位数里面最大的了, 这个已经无法更换了
  • 因此继续看百位, 即 481, 比它更大且只能用本身的数字那就是 841, 我们需要将 4 和 8 互换位置
  • 但我们发现, 它其实不是最小的, 还有一个位置可以更小, 那就是 1 跟 4 再做一次升序, 即把数字变成 814, 很明显比 841 要小
  • 因此一次的转换后, 从 13481 的下一个数就是 13814, 在这个过程里, 就涉及到了三个过程

总结来看:

  • 第一个过程寻找替换计数单位的下标, 也就是 4
  • 第二个过程寻找需要替换的值也就是把 4 替换成 8
  • 第三个过程升序操作也就是把 41 排序成 14
/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function (nums) {
  const n = nums.length

  let i = n - 2
  while (i >= 0 && nums[i + 1] <= nums[i]) {
    i--
  }

  if (i >= 0) {
    let j = n - 1
    while (j >= 0 && nums[j] <= nums[i]) {
      j--
    }

    swap(nums, i, j)
  }

  reverse(nums, i + 1)
}

/**
 * @param {number[]} nums
 * @param {number} i
 * @param {number} j
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var swap = function (nums, i, j) {
  const temp = nums[i]
  nums[i] = nums[j]
  nums[j] = temp
}

/**
 * @param {number[]} nums
 * @param {number} start
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var reverse = function (nums, start) {
  let i = start,
    j = nums.length - 1
  while (i < j) {
    swap(nums, i, j)
    i++
    j--
  }
}