Leetcode--Next Permutation

Leetcode--Next Permutation

Problem Description:

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

我們知道數字的權重從個位數開始增加，我們來看下154763的154763，4和6 。 從個位開始查找，6是第一個比4大的數，且4的位數比6大，如果交換這兩個數，總的值就會變大。

我們的找下一個排列的策略如下：

1.從個位開始往前查找，找到第一個逆序的值，154763中就是4。

2.再從個位開始往前查找，找到第一個比剛才逆序值大的數，這裡就是6。

3.交換兩個數最後會得到156743，我們發現156743並不是我們想要的數，因為156743比156347要大。

4.所以我們最後一步就是要對743進行排序，排成最小的347

5.有特殊情況，比如剛開始的數就是全逆序的，比如765431，那麼下一個值是134567.

class Solution {
public:
    void swapp(int *a,int *b)
{
    *a^=*b;
    *b^=*a;
    *a^=*b;
}

void nextPermutation(vector &num) {
        int len=num.size();
        int i,j;
        if(len==0)
            return;
        for(i=len-2;i>=0;i--)
            if(num[i]i;j--)
                if(num[j]>num[i])
                    break;

            swapp(&num[i],&num[j]);
            for(int s=i+1,p=len-1;s