0031._Next_Permutation.md

031. Next Permutation

难度: Medium

刷题内容

原题连接

• https://leetcode.com/problems/next-permutation/submissions/

内容描述

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

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

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

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(1)******

下一个排序与当前排序的关系是尽可能多的共用前面的位数

以[1,2,4,6,5,3]为例：

分为三个步骤

1. 从后向前查找，找到第一个升序排列的组合，即[4,6]，保存这个位置2（即4所在的位置）
2. 在这个位置上后面找到一个比他的数字进行调换——5，数组变为[1,2,5,6,4,3]，如果没有找到，则说明数组已经为最大的排列方式，直接翻转即可
3. 对于这个位置后面的数组([6,4,2])进行升序排列，数组变为[1,2,5,3,4,6]

代码：

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var nextPermutation = function(nums) {
  if (!nums || !nums.length || nums.length <= 1) {
    return nums
  }
  
  let index = -1;
  
  // step 1: 找到最大共有位置
  for (let i = nums.length - 1; i > 0; i--) {
    if (nums[i-1] < nums[i]) {
      index = i - 1;
      break;
    }
  }
  
  // 未找到的情况，翻转即可
  if (index === -1) {
    return nums.reverse();
  }
  
  // step 2: 替换最大共有位置上的值
  for (let i = nums.length - 1; i > index; i--) {
    if (nums[i] > nums[index]) {
      [nums[i], nums[index]] = [nums[index], nums[i]]
      break;
    }
  }
  
  // step 3: 最大共有位置之后的数据进行升序排列
  const afterList = nums.slice(index + 1)
  afterList.reverse()
  for (let i = index + 1; i < nums.length; i ++) {
    nums[i] = afterList[i - index - 1]
  }
};