LeetCode

LeetCode-31 下一个排列

nkul · 10月2日 · 2020年 22次已读

如上图所示,一组排列数,要找到下一个数,显然从个位开始变!

1、如果后面一段(上图黑色部分)是降序,显然这段降序已经是最大的数,找到下一个数显然不能再这里面的改动!
2、遇到第一个降序(上图蓝色部分),此时要变大,需要在后面降序中找到恰好比降序那个点大的数,交换位置!然后剩下数的升序即可!

此时,后半段还是降序–因为:
1、因为交换的是恰好比降序点大,所以后续的部分(红色之后)比降序点小!
2、红色到转折点显然也是比降序点要大的!

class Solution {
public:
    void nextPermutation(vector& nums) {
        int i = nums.size() - 1;
        //倒序找到第一个非降序的i
        while(i > 0 && nums[i - 1] >= nums[i]) i --;
        if(i <= 0){
            reverse(nums.begin(),nums.end());
        }else{
            //从i往后找第一个比i大的数!,注意此时的降序的点是i-1
            int k = i;
            //退出的条件是nums[k] <= nums[i - 1],故 k - 1才是恰好大于降序点的!
            while( k < nums.size() && nums[k] > nums[i - 1]) k++;
            swap(nums[i-1],nums[k - 1]);
            reverse(nums.begin()+i,nums.end());
        }
    }
};


0 条回应

必须 注册 为本站用户, 登录 后才可以发表评论!