31. 下一個排列
實作獲取下一個排列的函式，演算法需要將給定數字序列重新排列成字典序中下一個更大的排列，
如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列），
必須原地修改，只允許使用額外常數空間，
以下是一些例子，輸入位于左側列，其相應輸出位于右側列，1,2,3 → 1,3,23,2,1 → 1,2,31,1,5 → 1,5,1
解題思路：
如：[2, 4, 7, 5, 3, 2, 1]
這時我們需要判斷該數字的單調性，最簡單的就是從后向前依次判斷a[i] (nums.size() - 2) 是否小于 a[j] (nums.size() - 1) ，如果滿足條件依次向前遍歷， 如果不滿足條件則記錄 i 和 j 的位置，讓 i 再和從后到前的元素再比較一遍，一旦發現一個數字剛好大于 i， 則交換 i 和 那個位置(我們定義那個位置為k) 這時因為 j 前面的位置不受任何影響，所以不用考慮，只需要把 j 及它后面元素依次排序即可，如果出現一直滿足條件到第0位為止，說明它是以上完全逆序的陣列，與上一個問題重合，所以不做特殊考慮，直接排序，
1 class Solution { 2 public: 3 void nextPermutation(vector<int>& nums) { 4 if (nums.size() == 1) return ; 5 int i = nums.size() - 2; 6 int j = nums.size() - 1; 7 int k = nums.size() - 1; 8 while (i >= 0 && nums[i] >= nums[j]) { 9 i--; 10 j--; 11 } 12 if (i >= 0) { 13 while (nums[i] >= nums[k]) 14 k--; 15 swap(nums[i], nums[k]); 16 } 17 sort(nums.begin() + j, nums.end()); 18 } 19 };
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/661.html
標籤：其他