整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。
例如，arr = [1,2,3]，以下这些都可以视作 arr
的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1]。 整数数组的
下一个排列
是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的
下一个排列
就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。
例如，arr = [1,2,3]的下一个排列是 [1,3,2]。
类似地，arr = [2,3,1]的下一个排列是 [3,1,2]。
而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为
[3,2,1]不存在一个字典序更大的排列。 给你一个整数数组
nums ，找出 nums的下一个排列。
必须 原地 修改，只允许使用额外常数空间。
示例：
输入：nums = [1,2,3]
输出：[1,3,2]
思路：
这里考察我们对next_permutation函数的实现。我们直接调用这个函数就可以解决，但是我们还是希望可以自己手写一下这个函数。
“下一个排列”的定义是：给定数字序列的字典序中下一个更大的排列。如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。
我们以1,2,3为例，我们借用next_permutation函数输出全部排列。
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
28
29
30
31
32
33
34
35
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
class Solution {
public:
void nextPermutation(vector<int>& nums) {
sort(nums.begin(), nums.end());
do{
for(int i = 0; i < nums.size(); i++){
if(i == nums.size() - 1){
cout << nums[i] << endl;
}
else cout << nums[i] << " ";
}
}while(next_permutation(nums.begin(), nums.end()));
}
};
int main(){
int arr[3] = {1,2,3};
vector<int> nums(arr, arr + 3);
Solution a;
a.nextPermutation(nums);
for(int i = 0; i < nums.size(); i++){
cout << nums[i] << " ";
}
cout << endl;
return 0;
}
|
输出结果为：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1
1 2 3
算法推导:
可以把它抽象成一个整数，比如123下一个比它大的最小数就是132，我们为了得到这个数，肯定是考虑从后面开始遍历。
1、先找出最大的索引 k 满足 nums[k] <
nums[k+1]，如果不存在，就翻转整个数组，结束。
2、再找出另一个最大索引 l 满足 nums[l] > nums[k]；
3、交换 nums[l] 和 nums[k]；
4、最后翻转 nums[k+1:]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public:
void nextPermutation(vector<int>& nums) {
if(nums.size() <= 1) return;
int k = -1;
for(int i = nums.size() - 1, j = i - 1; j >= 0; i--, j--){
if(nums[j] < nums[i]){
k = j;
break;
}
}
if(k == -1){
reverse(nums.begin(), nums.end());
return;
}
for(int i = nums.size() - 1; i >= 0; i--){
if(nums[i] > nums[k]){
swap(nums[k], nums[i]);
break;
}
}
reverse(nums.begin() + k + 1, nums.end());
}
};
|