首页 > 其他 > 详细

LeetCode-31-Next Permutation

时间:2019-01-26 10:43:36      阅读:145      评论:0      收藏:0      [点我收藏+]

算法描述:

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 and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

解题思路:

1从后往前找第一个非升元素P。

2从后往前找第一个比P大的元素M, 将P和M交换。

3将交换后的M元素后的序列翻转。

    void nextPermutation(vector<int>& nums) {
        int index = nums.size()-2;
        while(index >=0 && nums[index+1] <= nums[index]) index--;
        if(index >= 0){
            int povit = nums.size()-1;
            while(povit >=0 && nums[index] >= nums[povit]) povit--;
            swap(nums[index],nums[povit]);
        }
        reversedata(nums,index+1,nums.size()-1);
    }
    void reversedata(vector<int>& nums, int left, int right){
        while(left < right){
            swap(nums[left],nums[right]);
            left++;
            right--;
        }
    }
};

 

LeetCode-31-Next Permutation

原文:https://www.cnblogs.com/nobodywang/p/10320901.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!