Leetcode 31 Next Permutation

triplebee

发布于 2018-01-12 15:08:41

7210

文章被收录于专栏：计算机视觉与深度学习基础计算机视觉与深度学习基础

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.

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

找到字典序的下一个排列.

偷懒做法

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(next_permutation(nums.begin(),nums.end())) return;
        sort(nums.begin(),nums.end());
    }
};

当然本着小题大做的原则，肯定不能这样放松要求哇。

算法原理查看 https://cloud.tencent.com/developer/article/1019302

找出从最右向左最长递增序列的左边一个元素，将最长递增序列逆置，这样得到的是该序列的最小字典序排列，再将找到的左边一个元素和该序列中大于它的最小一个元素交换位置。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        if(nums.size()<2) return ;
        for(int i=nums.size()-1;i>0;i--)
            if(nums[i]>nums[i-1])
            {
                reverse(nums.begin()+i,nums.end());
                vector<int>::iterator it=upper_bound(nums.begin()+i,nums.end(),nums[i-1]);
                swap(*it,nums[i-1]);
                return ;
            }
        reverse(nums.begin(),nums.end());
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2016-09-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

memory