runtime 0 ms, beats 100% of cpp submissions
O(n) solution with explanation

tags: none

Next Permutation

📖 description

給定一個陣列，回傳他的 next permutation ，如果已經是遞減排序，輸出的遞增排序。

ex. 
    1 2 3 -> 1 3 2
    3 2 1 -> 1 2 3 (遞減排序 -> 遞增排序)
    1 1 5 -> 1 5 1

🧠 solution

單純跟 c++ 的 next permutation 一樣，主要的邏輯是

  1. 先從尾巴往前找到第一個大於下一個元素的位置，表示可以互換
    • (ex. 2 5 1 發生了) 5>2
  2. 如果找到底了都沒有代表此陣列是遞減排序，回傳遞增排序的結果
    • 3 2 1 -> 1 2 3 (遞減排序 -> 遞增排序)
  3. 從尾巴找過的地方挑一個最大的值出來，並與之前挑出來的位置互換
    • (ex. 2 5 1 -> 5 2 1) 把 5 跟 2 互換
  4. 把互換位置後面的 sort 一次元素，讓後方的順序保持最小
    • (ex. 5 2 1 -> 5 1 2) 把 2 1 排序成 1 2

⏳ time complexity

遍歷一次元素複雜度 O(n) ， sort 後面的元素時間複雜度 O(nlog(n))
總時間複雜度 O(nlog(n))

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public:
    void nextPermutation(vector<int>& n) {
        int i,j,mi=INT_MAX,po;
        int m=n.size();
        for(i=m-1;i>0;i--){
            if(n[i]>n[i-1]) break;      // 找到交換點 index
        }
        if(i==0){                       // 如果該陣列是遞減排序
            int l=(m+1)/2;
            for(int k=0;k<l;k++){       // 將陣列換成遞增排序
                swap(n[k],n[m-k-1]);
            }
            return;
        }
        else{
            for(j=i;j<m;j++){           // 在 index 後方找一個最大的數值替換
                if(n[j]>n[i-1]){
                    mi=min(mi,n[j]);
                    po=j;
                }
            }
            swap(n[po],n[i-1]);         
            sort(n.begin()+i,n.end());  // 將後方的元素以小排到大
        }
    }
};