# 31 - Next Permutation

解法一 - C++ 內建 next_permutation API

這個解法算是有點作弊，不過滿好玩的，所以就用用看：

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

效率也不差： Runtime: 8 ms, faster than 75.35% of C++ online submissions for Next Permutation. Memory Usage: 8.5 MB, less than 97.85% of C++ online submissions for Next Permutation.

解法二 - 利用第一個 nums[i] < nums[i+1] 的地方

我們可以先觀察一下例子，發現到

1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

這些例子都只 swap 了兩個數字，就得到了答案。

再仔細觀察一下，會發現 swap 的重點是所有數字裡面最大的那一個，讓我們先大膽假設可以 swap 最大數字跟這個最大數字的往前一位。不過這個假設有點大膽，讓我們隨便舉個例子來檢查一下：

1,1,3,2 → 1,2,1,3

因為 32 已經是以 11 開頭的最大數字了，所以下一個就必須要把 index 1 的 1 換掉，把 2 移到前面。基本上到這邊已經違反我們剛剛的假設，不過倒是發現了另一個有趣的性質，就是

當我們看到 nums[i] < nums[i+1] 時，nums[i+1]到nums[n-1]是遞減的。

例如 1,1,3,2，當我們看到 1 比 3 小時，就知道從 3 之後的都已經是遞減的了(或說是 reversely sorted 了)。

這時候我們應該要

把 nums[i+1] 到 nums[n-1] 裡面比 nums[i] 大的最小值，跟 nums[i] 的值交換，然後把 nums[i+1] 到 nums[n-1] 重新 sort 成遞增排序

最後只要再考慮 3,2,1 這種情況，只要找到最前面都還沒有發現 nums[i] < nums[i+1]，那就表示目前已經是最大排序，那直接 reverse 就好。

實作如下：

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        int n = nums.size();
        if(n < 2) return ;

        int index = n-1;
        while(index) {
            if(nums[index-1] < nums[index])
                break;
            index--;
        }

        if(index == 0) {
            sort(nums.begin(), nums.end());
        }
        else {
            int i = index-1;

            // swap nums[i] with smallest num bigger than nums[i] in nums[i+1] - nums[n-1]
            int j = i+1, val = INT_MAX;
            for(int k=i+1; k<n; k++) {
                if(nums[k]<val && nums[k]>nums[i]){
                    j = k;
                    val = nums[k];
                }
            }
            swap(nums[i], nums[j]);


            sort(nums.begin()+i+1, nums.end());
        }


    }
};

Runtime: 8 ms, faster than 75.35% of C++ online submissions for Next Permutation. Memory Usage: 8.5 MB, less than 100.00% of C++ online submissions for Next Permutation.