[Leetcode]Next Permutation

No.31 Next Permutation

这道题主要是全排列问题，输出某一个数字序列的全排列的下一个情况，比如说1,2,3全排列的下一个是1,3,2。

全排列的顺序按字典序排列，比如123的全排列顺序为：

123 132 213 231 312 321

当然最笨的方法还是生成所有全排列然后找。

这道题是有固定的算法的。

以下摘自网上的算法：

算法思想：举例如下

    输入：1 4 6 5 3 2

    step1：从右往左找到第一个破坏升序(非严格)的元素，此例中为4.记下标为 i

    step2: 依然从右往左,找到第一个大于4的元素，此例中5，交换4和5.

    step3：从i+1到最右端，逆置。6 4 3 2 to 2 3 4 6

    so,1 5 2 3 4 6 即为所求。

把全排列的非递归算法滤一遍大概就懂了，因为全排列相当于从最小的数字开始固定在前面的某一位上，因此从右往左找的第一个逆序就是应该替换的位置，比如 1 2 3 4 5这个串，把1固定在最前面，后面全排序2 3 4 5，再把2固定到第二位，后面全排序3 4 5，以此类推，第一个出来的是12345，然后回溯的时候先把4和5颠倒变成12354。发现第一次逆序就说明后面的已经到全排列的最后一个了。

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int pos=-1;
        int numLen=nums.size()-1;
        for(int i=numLen;i>0;i--){
            if(nums[i]>nums[i-1]){
                pos=i-1;
                break;
            }
        }
        if(pos==-1){
            reverse_num(nums,0,numLen);
            return;
        }
        int pos_num=nums[pos];
        for(int i=numLen;i>pos;i--){
            if(nums[i]>pos_num){
                nums[pos]=nums[i];
                nums[i]=pos_num;
                break;
            }
        }
        reverse_num(nums,pos+1,numLen);
    }
    void reverse_num(vector<int>& nums,int begin, int end){
        while(begin<end){
            int temp=nums[begin];
            nums[begin]=nums[end];
            nums[end]=temp;
            begin++;
            end--;
        }
    }
};