题目描述
返回最小的比他大的那个数
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
样例
[1,2,3]
[1,3,2]
---
[1,1,5]
[1,5,1]
算法1
(暴力) $O(n)$
时间复杂度
参考文献
C++ 代码
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k = nums.size() - 1;
while (k > 0 && nums[k - 1] >= nums[k]) k --;
if (k <= 0){
reverse(nums.begin(), nums.end()); //如果都是降序,(它就是最大的数)返回最小的即可,反转
} else{
int t = k;
while (t < nums.size() && nums[t] > nums[k - 1]) t ++; //注:t要比数列长度小,不然会越界。比k大的最小的数
swap(nums[t - 1], nums[k - 1]); //交换t位和k位
reverse(nums.begin() + k, nums.end());//k位之后的重新排序,由于是第一个上升子端,k后面的都是降序,所以反过来即可变成最小的排序
}
}
};