31.下一个排列

链接：31.下一个排列
难度：Medium
标签：数组、双指针
简介：实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

题解 1 - typescript

• 编辑时间：2020-11-10
• 执行用时：96ms
• 内存消耗：40MB
• 编程语言：typescript
• 解法介绍：计算最小改动数，逆序遍历检测递增。

function nextPermutation(nums: number[]): void {
  const len = nums.length;
  const swap = (i1: number, i2: number) => {
    const t = nums[i1];
    nums[i1] = nums[i2];
    nums[i2] = t;
  };
  const reverse = (left: number) => {
    let right = len - 1;
    while (left < right) {
      swap(left, right);
      left++;
      right--;
    }
  };
  let i = len - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }
  if (i >= 0) {
    let j = len - 1;
    while (j >= 0 && nums[i] >= nums[j]) {
      j--;
    }
    swap(i, j);
  }
  reverse(i + 1);
}