[LeetCode][Medium] 31. Next Permutation

Leetcode 網址: https://leetcode.com/problems/next-permutation/

題目說明:

題目的大致意思是給定一組數字，請將這組數字重新排列組合得到一個比原先數字大的排列，

假設給定的數字為 1 2 3，那麼 1 3 2 就是這個題目想要的答案，

假設給定的數字為 1 3 2，那麼 2 1 3 就是這個題目想要的答案。

Note: 題目要求空間複雜度為 O(1)

解題說明:

這題透過題目的敘述及觀察皆可以發現，我們要換的數字最好是越後面的位數越好，

假設我們找到可以透過替換第 8 位達成，那前面的第 1 ~ 7 位都不需要管它了，

因此我們要從後面去掃哪一個位數可以被替換，

假設今天要替換第 8 位數，我們只要有第 9 ~ n 位數中比第 8 位數大的數字即可，

至於要替換成哪個數字，想當然就是比第 8 位數大但卻是第9 ~ n 位數中最小的數字，

因此將以上的想法寫成程式即可，不過值得注意是替換完成之後不代表是正確答案，

例如: 1 3 2 透過以上算法得到會是 2 3 1，但實際上答案是 2 1 3，

因此我們再透過把後面的數字排序即可，

以上的時間複雜度為 O(n * n + n log n) = O(n * 2)，

另外以上的算法很直覺但少用了一些題目的特性，考慮題目特性後可以優化成 O(n)，

詳細優化的算法可以參考 這篇

程式碼

void nextPermutation(vector<int>& nums) {
        int index = nums.size() - 1;
        while (index > 0 && nums[index - 1] >= nums[index]) index--;
        if (index > 0) {
            int minIndex = index;
            for (int i = index; i < nums.size() && nums[i] > nums[index - 1]; i++) minIndex = i;
            swap(nums[index - 1], nums[minIndex]);
        }
        reverse(nums.begin() + index, nums.end());
        return;
        
        /*
        int index = 0;
        for (int i = nums.size() - 2; i >= 0; i--) {
            int minIndex = -1;
            for (int j = nums.size() - 1; j > i; j--) {
                if (nums[j] > nums[i]) {
                    minIndex = minIndex == -1 ? j : (nums[j] < nums[minIndex] ? j : minIndex);
                }
            }
            if (minIndex != -1) { swap(nums[i], nums[minIndex]); index = i + 1; break; }
        } 
        sort(nums.begin() + index, nums.end());
        return;
        */
    }

結果

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Next Permutation.

Memory Usage: 12.1 MB, less than 78.33% of C++ online submissions for Next Permutation.