Voyz's Studio.

LeetCode算法笔记--下一个排列

字数统计: 388阅读时长: 1 min
2020/12/05 Share

LeetCode算法笔记–Day36

31. Next Permutation

题目:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

My Answer:

方法一:扫描

e56a66ed318d1761cd8c8f9d1521f82a30c71ecc84f551912b90d8fe254c8f3d-image.png

  • 1.从后向前查找第一个相邻升序的元素对 (i,j),满足 A[i] < A[j]。此时 [j,end) 必然是降序.

  • 2.在 [j,end) 从后向前查找第一个满足 A[i] < A[k] 的 k。A[i]、A[k] 分别就是上文所说的「小数」、「大数」.

  • 3.将 A[i] 与 A[k] 交换.

  • 4.可以断定这时 [j,end) 必然是降序,逆置 [j,end),使其升序.

  • 5.如果在步骤 1 找不到符合的相邻元素对,说明当前 [begin,end) 为一个降序顺序,则直接跳到步骤 4

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* @param {number[]} nums
* @return {void} Do not return anything, modify nums in-place instead.
*/
var nextPermutation = function(nums) {
let i=-1,j=-1;
// 从后向前获取第一组相邻升序的坐标
for(let _p = nums.length-1;_p>=0;_p--){
if(nums[_p]>nums[_p-1]){
i = _p-1;
j = _p;
break;
}
}
// 最大排列则返回最小排列
if(i<0) return nums.reverse();
// 从后向前获取第一个大于nums[i]的值与之交换
for(let _p = nums.length-1;_p>=j;_p--){
if(nums[_p]>nums[i]){
nums[_p] = [nums[i],nums[i]=nums[_p]][0];
break;
}
}
// j之后的降序变升序
return nums.slice(0,j).concat(nums.slice(j).reverse())

};
CATALOG
  1. 1. LeetCode算法笔记–Day36
  2. 2. 31. Next Permutation
    1. 2.1. 题目:
    2. 2.2. My Answer:
      1. 2.2.1. 方法一:扫描