leetcode 31 Next Permutation

题目

https://leetcode.com/problems/next-permutation/

思路

从低位开始寻找递增数列,边界,即递增数列是无法变小的,找到边界后,从递增数列中寻找大于边界值的最小值进行交换,而后对面的数进行排序使其最大

源码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int i = nums.size()-2;
        for(;i >= 0;--i){
            if(nums[i]<nums[i+1]){
                for(int j = nums.size()-1;j > i;--j){
                    if(nums[j]>nums[i]){
                        cout << j;
                        int t = nums[j];
                        nums[j]=nums[i];
                        nums[i]=t;
                        sort(nums.begin()+i+1,nums.end());
                        i=-1;
                        break;
                    }
                }
            }

        }
        if(i!=-2){
            // sort(nums.begin(),nums.end());
            reverse(nums.begin(),nums.end());
        }
    }
};

我的另一份代码

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        //倒着扫描递增序列怎么改都是会变小,找到非递增的数,用后面的最接近它的数交换,sort
        //插入排序?


        //我的想法时,改变最小数量级的位置,即替换十位,替换百位,替换千位。。。
        //那么从十位开始考虑是否该位为非递增位,是则为替换位一共考虑n-1位
        //每次考虑时,从最低位开始找比该位大的,因为后面是递增的一定要从低位最小的数找起才能保证变化最小
        int n = nums.size();
        int end;
        bool can=false;
        for(int i = 1;i <= n - 1; ++i){
            int j = n-1;
            int step = i;
            while(step--){
                if(nums[j]>nums[n-i-1]){
                    int temp = nums[j];
                    nums[j]=nums[n-i-1];
                    nums[n-i-1]=temp;
                    can = true;
                    end = n-i-1;
                    break;
                }
                j--;
            }
            if(can)break;

        }
        cout << end <<endl;
        if(can)
            sort(nums.begin()+end+1,nums.end());
        else
            sort(nums.begin(),nums.end());

    }
};

发表评论

邮箱地址不会被公开。 必填项已用*标注