LeetCode-31-Next-Permutation
LeetCode-31-Next-Permutation
小二三不乌
发布于 2018-08-02 10:23:53
发布于 2018-08-02 10:23:53
LeetCode-31-Next-Permutation
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory.
这个排序主要是有两种情况，一个是类似于3 1 2这样的情况，直接从后往前找到第一个nums[i]<nums[i-1]的，然后把i记下来，再与后面第一个小于i的k调换顺序之后，对i后面的进行反转排序就好了。
另一种情况是：已经反转成功了，类似3 2 1，需要直接置为最开始的状态，处理方式是，依旧从后往前找i,如果没有找到的话，就可以直接将序列反转即可。
代码如下：
class Solution {
public:
void nextPermutation(vector<int>& nums) {
int k=-1;
for(int i=nums.size()-2;i>=0;--i){
if(nums[i]<nums[i+1]){
k=i;
break;
}
}
if(k==-1){
reverse(nums.begin(),nums.end());
return;
}
int l=0;
for(int i=nums.size()-1;i>k;--i){
if(nums[i]>nums[k]){
l=i;
break;
}
}
swap(nums[l],nums[k]);
reverse(nums.begin()+k+1,nums.end());
}
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录