LeetCode31 下一个排列

链接: https://leetcode-cn.com/problems/next-permutation/

题意

给你一个整数数组 nums ,找出 nums 的下一个排列。整数数组的 下一个排列 是指其整数的下一个字典序更大的排列。

解法

将序列视为数字,以3个数的全排列为例
123, 132, 213, 231, 312, 321
每次下一个数字是要比上一个数大,但是增大的幅度要求是最小的

来源:https://www.jianshu.com/p/b31f54cf0c54
因此可以考虑如下的算法:

  1. 从右到左进行扫描,发现第一个违背递增趋势的数字,称之为 PartitionNumber, 如上图,6恰好是我们找到的 PartitionNumber .
  2. 从右到左进行扫描,发现第一个比 PartitionNumber 要大的数,称之为 ChangeNumber.而7恰好是我们找到的 ChangeNumber ,需要注意的是,这样的数一定是存在的,否则的话,就找不到所以的 PartitionNumber 了.
  3. 交换 PartitionNumber 和 ChangeNumber.这样一步,会使得新的排列组成的数比旧的排列组成的数要大,当然,新数增长的幅度不一定是最小的.
  4. 反转在 PartitionNumber 右侧的数.此时, PartitionNumber 右侧的排列已经是严格的从大到小排列了,如此反转之后,可以保证,新的排列组成的数的增长幅度在所有的可能中最小.

代码

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
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int n = nums.size();
int partition = -1, change = 0;
for (int i = n - 1; i > 0; i--) {
if (nums[i - 1] < nums[i]) {
partition = i - 1;
break;
}
}
if (partition != -1) {
for (int i = n - 1; i > 0; i--) {
if (nums[i] > nums[partition]) {
change = i;
break;
}
}
swap(nums[partition], nums[change]);
}
reverse(nums.begin() + partition + 1, nums.end());

return;
}
};