31. Next Permutation

這題搞爆我了, 但我得承認他是一題很好的練習題

首先, 我們花了點時間搞懂題目(不得不說這英文要有一定水平才看得懂)

大意是這樣的
[1, 2, 3]的排列組合裡有

[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]

假設他給你[2, 1, 3] 你必須想辦法生出他的下家[2, 3, 1]給他
但到底要怎麼選呢?

首先, 我們得從後面開始看, 我們舉例 [5, 6, 4, 3, 2, 1]
從後面看過來, 發現在6跟5之間斷了遞增, 如此一來我們便可以確定[4, 3, 2, 1]是不能動的, 而首先我們先把5這個數給抓起來, 在來我們一樣再從後面找, 找到一個在5之後的數, 且這個數大於5, 這邊很快的我們發現那個數是6, OK我們抓取5跟6, 然後互換 變成

[6, 5, 4, 3, 2, 1]
但因為6之後的數變新的排列, 故我們做sort讓他從頭來過(只sort 6之後)
[6, 1, 2, 3, 4, 5]
這邊有人提出用reverse就好了, 都可以

這樣就完成了, 程式碼其實要撰寫真的是要一直去注意index, 有個比較陷阱的地方就是遞增數列在跑的時候, 這個非嚴格遞增, 所以相同的數字我們必須照樣往下找
這樣在[1,5,1]這個測資才不會出現卡住的問題

class Solution {
public:
 void nextPermutation(vector<int>& nums) {
 int tmp = INT_MAX;
 if(nums.size() <= 2) {
 reverse(nums.begin(), nums.end());
 return; }
 
 int i = nums.size()-1;
 while(i>=1 && nums[i-1]>=nums[i]) i--;
 if(i == 0){
 reverse(nums.begin(), nums.end());
 return;
 }
 i--;
 int j = nums.size() -1;
 while(j>i && nums[i]>=nums[j]) j--;
 
 swap(nums[i], nums[j]);
 sort(nums.begin()+i+1, nums.end());
}
};