Skip to content

Latest commit

 

History

History
85 lines (59 loc) · 2.19 KB

0031._Next_Permutation.md

File metadata and controls

85 lines (59 loc) · 2.19 KB

031. Next Permutation

难度: Medium

刷题内容

原题连接

内容描述

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

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

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

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。 1,2,31,3,2 3,2,11,2,3 1,1,51,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]
  }
};