0031. 下一個排列 · ttttt

# 0031. 下一個排列 ## 題目地址(31. 下一個排列) <https://leetcode-cn.com/problems/next-permutation/> ## 題目描述 ``` <pre class="calibre18">``` 實現獲取下一個排列的函數，算法需要將給定數字序列重新排列成字典序中下一個更大的排列。如果不存在下一個更大的排列，則將數字重新排列成最小的排列（即升序排列）。必須原地修改，只允許使用額外常數空間。以下是一些例子，輸入位于左側列，其相應輸出位于右側列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 ``` ``` ## 前置知識 - 回溯法 ## 公司 - 阿里 - 騰訊 - 百度 - 字節 ## 思路符合直覺的方法是我們按順序求出所有的排列，如果當前排列等于 nums，那么我直接取下一個但是這種做法不符合 constant space 要求（題目要求直接修改原數組）,時間復雜度也太高，為 O(n!),肯定不是合適的解。這種題目比較抽象，寫幾個例子通常會幫助理解問題的規律。我找了幾個例子，其中藍色背景表示的是當前數字找下一個更大排列的時候`需要改變的元素`. ![](https://img.kancloud.cn/2f/15/2f152b5947d92fc853c6b279c2a3ff72_465x252.jpg) 我們不難發現，藍色的數字都是從后往前第一個不遞增的元素，并且我們的下一個更大的排列只需要改變藍色的以及之后部分即可，前面的不需要變。那么怎么改變藍色的以及后面部分呢？為了使增量最小，由于前面我們觀察發現，其實剩下的元素從左到右是遞減的，而我們想要變成遞增的，我們只需要不斷交換首尾元素即可。另外我們也可以以回溯的角度來思考這個問題，讓我們先回溯一次： ![](https://img.kancloud.cn/a5/0d/a50de4539ee5c6ae55819e823dba085c_470x171.jpg) 這個時候可以選擇的元素只有2，我們無法組成更大的排列，我們繼續回溯，直到如圖： ![](https://img.kancloud.cn/f4/b7/f4b70343ffe694cd64dcc50b9f56d45c_600x270.jpg) 我們發現我們可以交換4或者2實現變大的效果，但是要保證變大的幅度最小（下一個更大），我們需要選擇最小的，由于之前我們發現后面是從左到右遞減的，顯然就是交換最右面大于1的。之后就是不斷交換使之幅度最小： ![](https://img.kancloud.cn/7a/a6/7aa69c5c9d130f585524a735ec23b29a_612x454.jpg) ## 關鍵點解析 - 寫幾個例子通常會幫助理解問題的規律 - 在有序數組中首尾指針不斷交換位置即可實現reverse - 找到從右邊起`第一個大于nums[i]的`，并將其和nums\[i\]進行交換 ## 代碼 - 語言支持: Javascript，Python3 ``` <pre class="calibre18">``` /* * @lc app=leetcode id=31 lang=javascript * * [31] Next Permutation */ function reverseRange(A, i, j) { while (i < j) { const temp = A[i]; A[i] = A[j]; A[j] = temp; i++; j--; } } /** * @param {number[]} nums * @return {void} Do not return anything, modify nums in-place instead. */ var nextPermutation = function(nums) { // 時間復雜度O(n) 空間復雜度O(1) if (nums == null || nums.length <= 1) return; let i = nums.length - 2; // 從后往前找到第一個降序的,相當于找到了我們的回溯點 while (i > -1 && nums[i + 1] <= nums[i]) i--; // 如果找了就swap if (i > -1) { let j = nums.length - 1; // 找到從右邊起第一個大于nums[i]的，并將其和nums[i]進行交換 // 因為如果交換的數字比nums[i]還要小肯定不符合題意 while (nums[j] <= nums[i]) j--; const temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } // 最后我們只需要將剩下的元素從左到右，依次填入當前最小的元素就可以保證是大于當前排列的最小值了 // [i + 1, A.length -1]的元素進行反轉 reverseRange(nums, i + 1, nums.length - 1); }; ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def nextPermutation(self, nums): """ Do not return anything, modify nums in-place instead. :param list nums """ # 第一步，從后往前，找到下降點 down_index = None for i in range(len(nums)-2, -1, -1): if nums[i] < nums[i+1]: down_index = i break # 如果沒有下降點，重新排列 if down_index is None: nums.reverse() # 如果有下降點 else: # 第二步，從后往前，找到比下降點大的數，對換位置 for i in range(len(nums)-1, i, -1): if nums[down_index] < nums[i]: nums[down_index], nums[i] = nums[i], nums[down_index] break # 第三部，重新排列下降點之后的數 i, j = down_index+1, len(nums)-1 while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 ``` ``` Python3 Code: ``` <pre class="calibre18">``` class Solution: def nextPermutation(self, nums): """ Do not return anything, modify nums in-place instead. :param list nums """ # 第一步，從后往前，找到下降點 down_index = None for i in range(len(nums)-2, -1, -1): if nums[i] < nums[i+1]: down_index = i break # 如果沒有下降點，重新排列 if down_index is None: nums.reverse() # 如果有下降點 else: # 第二步，從后往前，找到比下降點大的數，對換位置 for i in range(len(nums)-1, i, -1): if nums[down_index] < nums[i]: nums[down_index], nums[i] = nums[i], nums[down_index] break # 第三步，重新排列下降點之后的數 i, j = down_index+1, len(nums)-1 while i < j: nums[i], nums[j] = nums[j], nums[i] i += 1 j -= 1 ``` ``` ## 相關題目 - [46.next-permutation](46.next-permutation.md) - [47.permutations-ii](47.permutations-ii.html) - [60.permutation-sequence](60.permutation-sequence.html)(TODO)