Keshawn_lu's Blog

Leetcode 31. 下一个排列

字数统计: 576阅读时长: 2 min
2020/11/10 Share

题目简介:

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

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

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

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。

1
2
3
1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

思路:

这题看了题解以后感觉还是有点懵懵的,像是脑筋急转弯题一样,下面是个人的一点理解。

首先是从后往前遍历,找到第一个破坏升序的元素位置pos(即nums[pos ... ]为降序数组),由于降序是最大的序列,所以我们先将后面降序的数组翻转,这样就变成了最小的升序数组了。

来个例子会更加清楚一点,如[5,7,6,4,3] -> [6,3,4,5,7],由于原数组是5开头的最大数组了,所以下一个排列必是6开头的,并且6后面的数组必是最小的升序

所以我们先将nums[pos ...]翻转,变成[5,3,4,6,7],然后在升序数组[3,4,6,7]中找到第一个比5的数字6(同样也是最接近5的数),将其与5交换,从而变成了[6,3,4,5,7],可以注意到,交换以后,原来是升序的数组现在还是升序的,说明这就是最小的组合了。

tip:

  • pos == 0时,说明原本数组是最大的排列,下一个排列只需将其翻转,就是最小的升序了。

代码如下:

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
class Solution {
public:
void nextPermutation(vector<int>& nums) {

int pos = nums.size() - 1;

while(pos > 0 && nums[pos] <= nums[pos - 1]) //注意是<=
pos--;

reverse(nums.begin() + pos, nums.end()); //翻转后面的降序为升序

//原本数组一直是降序(最大),下一个排列便为翻转后的升序(最小)
if(pos == 0)
return;

for(int i = pos; i < nums.size(); i++){

if(nums[i] > nums[pos - 1]){

//找到第一个比nums[pos - 1]大的数(也是最接近的)
swap(nums[i], nums[pos - 1]);
break;
}
}
}
};
CATALOG
  1. 1. 题目简介:
  2. 2. 思路:
  3. 3. 代码如下: