题目链接
https://leetcode.com/problems/next-permutation/
解题思路
拿一个例子来说明,如下:
7, 5, 1, 2, 6, 3, 0
- 从后往前找第一个相邻两个元素后一个元素大于前一个元素,也就是2和6
- 在2后面也是从右往前周第一个大于2的数,也就是3
- 交换2和3
7, 5, 1, 3, 6, 2, 0
- 对3后面的数转置一下,就可以得到答案
7, 5, 1, 3, 0, 2, 6
在第1步找到的2和6,2之后的数肯定是降排,在第2和3步之后,3后面的数仍然满足降排性质,所有在对3后面的数进行转置得到一个升排就是答案。
代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
if (nums.size() < 2) {
return;
}
//从后往前找第一个符合nums[i] > nums[i - 1]
for (int i = nums.size() - 1; i > 0 ; i--) {
if (nums[i] > nums[i - 1]) {
//在nums[i - 1]之后找比nums[i - 1]大且最小的数进行交换
for (int k = nums.size() - 1; k >= i ; --k) {
if (nums[k] > nums[i - 1]) {
swap(nums[i - 1], nums[k]);
break;
}
}
//转置下
reverse(nums.begin() + i, nums.end());
return;
}
}
reverse(nums.begin(), nums.end());
}
};
网友评论