031 - Next Permutation

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

Hide Tags

Array

Hide Similar Problems

(M) Permutations (M) Permutation Sequence

 

以前做的，因为做到类似的题目，扒出来看看。
思路是从后往前找，找到第一个相对其后变小（下降）的数字，作为待交换对象，
然后在从后往前找，看从末尾到这个数字之间的第一个出现的比它大的数字，他们俩就是我们要交换的对象了。
交换之后，它后面的部分肯定是降序的，这就是说，后面这部分还可以更小。
要尽可能保持小的尾部，那就把这些数字reverse一下好叻，这样就得到最近的大一点的数字了。

看的过程中深感代码冗长，逐步做了些简化，依次去掉了各种辅助的变量，利用循环变量本身，就足够进行判断了。
优化之后的代码看起来简洁多了，可读性不但没有变差，反而变好了。

所以，写完代码一定要多review，尽可能简化，改进逻辑！！

//--------------------------------- old codes ---------------------------------
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(2>num.size())
            return;
        int found=0;
        int sz=num.size();
        //from backward, find first element who has a smaller one before it.
        int idbk=sz-1, bk=num[idbk];
        for(int nn=sz-1; nn>0; nn--)
        {
            if((num[nn])>(num[nn-1]))
            {
                idbk=nn-1;
                bk=num[nn-1];
                found=1;
                break;
            }
        }

        //from backward, find first element bigger than this one,
        //that's the closest bigger digit we need.
        int idbg=sz-1, bg=num[idbg];
        for(int nn=sz-1; nn>idbk; nn--)
        {
            if((num[nn])>bk)
            {
                idbg=nn;
                break;
            }
        }

        if(found)
        {
            //swap them
            swapme(num, idbk, idbg);
            //sort the rest part after bk
            reserve(num, idbk+1, sz-1);
        }
        else
            reserve(num, 0, sz-1);
        return;
    }
   
    void reserve(vector<int> &v, int start, int end)
    {
        for(int ii=0; ii<(end-start+1)/2; ii++)
        {
            swapme(v, start+ii, end-ii);
        }
        return;
    }
   
    void swapme(vector<int> &v, int a, int b)
    {
        v[a]=(v[a])^(v[b]);
        v[b]=(v[a])^(v[b]);
        v[a]=(v[a])^(v[b]);
        return;
    }
};
14 ms.

 

//---------------------------------  simplified codes ---------------------------------
class Solution {
public:
    void nextPermutation(vector<int> &num) {
        if(2>num.size())
            return;
        int sz=num.size(), idx1=sz-2, idx2=sz-1, bk=num[sz-1];

        //from backward, find first digit (num[idx1]) smaller than its successor.
        for(; idx1>=0; idx1--)
            if((num[idx1])<(num[idx1+1]))
                break;

        //from backward, find the smallest (closest) digit bigger than num[idx1]
        for(; idx2>idx1; idx2--)
            if((num[idx2])>num[idx1])
                break;

        //swap them
        if(idx1>=0)
            swapme(num, idx1, idx2);

        //sort the rest part in descending order (after necessary swap of idx1 idx2)
        int start = (idx1>=0) ? idx1+1 : 0;
        reserve(num, start, sz-1);
       
        return;
    }
   
    void reserve(vector<int> &v, int start, int end)
    {
        for(int ii=0; ii<(end-start+1)/2; ii++)
            swapme(v, start+ii, end-ii);
        return;
    }
   
    void swapme(vector<int> &v, int a, int b)
    {
        v[a]=(v[a])^(v[b]);
        v[b]=(v[a])^(v[b]);
        v[a]=(v[a])^(v[b]);
        return;
    }
};
12 ms.