题目描述
实现获取 下一个排列 的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列（即，组合出下一个更大的整数）。 如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。 必须 原地 修改，只允许使用额外常数空间。
Example 1:
输入：nums = [1,2,3] 输出：[1,3,2]
Example 2:
输入：nums = [3,2,1] 输出：[1,2,3]
Example 3:
输入：nums = [1,1,5] 输出：[1,5,1]
Example 4:
输入：nums = [1] 输出：[1]
Constraints:
- 1 <= nums.length <= 100
- 0 <= nums[i] <= 100
解题思路
- 先找到不是递减的位置 i
- 从后面开始，找到第一个不小于 nums[i] 的位置 j
- 交换 nums[i], nums[j]
- 交换 nums[i] 以及后面的序列
C++代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int i = nums.size() - 2;
while(i >= 0 && nums[i] >= nums[i + 1]){
i--;
}
if(i >= 0){
int j = nums.size() - 1;
while(j >= 0 && nums[i] >= nums[j]){
j--;
}
swap(nums[i], nums[j]);
}
reverse(nums.begin() + i + 1, nums.end());
}
};
