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.

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

Difficulty: Medium

一开始没看懂题,参考grandyang的解法才看懂.先看下全排列,如果给出的为[1,2,3]那么全排列为[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].这道题让我们求下一个排列的顺序,从题目中的列子可以看出,如果给定的数组为降序如[3,2,1],那说明为全排列的最后一个情况,则下一个排序就是最初始的情况[1,2,3].再来看下面一个例子,给出数组

1 2 7 4 3 1

下一个排序为

1 3 1 2 4 7

从末尾往前看,数字逐渐变大,到了2才减小的,然后我们再从后往前找第一个比2大的数字,是3,交换2和3的位置,再把3以后的数字转置一下便可得到.

解法1

上面的分析

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

解法2

上面解法的简洁瞎发,思路一样

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size(),i=n-2,j=n-1;
        while(i>=0&&nums[i]>=nums[i+1]) --i;
        if (i >= 0)
        {
            while (nums[j]<=nums[i]) --j;
            swap(nums[i],nums[j]);
        }
        reverse(nums.begin()+i+1,nums.end());
    }
};
 
comments powered by Disqus