Last Updated on 2021-01-31 by Clay
題目
Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.
If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).
The replacement must be in place and use only constant extra memory.Example:
Input: nums = [1,2,3]
Output: [1,3,2]
Input: nums = [3,2,1]
Output: [1,2,3]
Input: nums = [1,1,5]
Output: [1,5,1]
Input: nums = [1]
Output: [1]題目給定輸入一個陣列，我們要將陣列排列成『下一個較大的值』。比方說題目輸入了 [1,2,3]，那麼我們就不能排列成 [3,1,2]、而是要排列成 [1,3,2] —— 因為 132 才下一個較大的值，而非 312。
而當題目給定的陣列沒有下一個較大的排列時，則將陣列『從小排到大』。
順帶一提這題不會返回任何值，直接處理輸入陣列即可。
解題思路
我的想法很單純：
- 從陣列最右邊開始一個個搜尋，若是第 i 個值比第 i+1 個值來得更小，則從 i 開始往右側找尋比『第 i 個值』大的值當中的『最小值』
- 交換第 i 個值以及比第 i 個值大的最小值
- 從原本 i 的位置往右，將全部的值從最小到最大排序
- 如此一來，我們就能得到『下一個較大的排列』
C++ 程式碼
class Solution { public: void nextPermutation(vector<int>& nums) { // Init int min_v = 101; int min_p = -1; int p = -1; for (int i=nums.size()-2; i>=0; i--) { if (nums[i] < nums[i+1]) { p = i; // Find the min_p for (int j=p+1; j<nums.size(); j++) { if (nums[i] < nums[j] && nums[j] < min_v) { min_p = j; min_v = nums[j]; } } break; } } // Have next permutation if (p != -1) { swap(nums[p], nums[min_p]); sort(nums.begin()+p+1, nums.end()); } else { sort(nums.begin(), nums.end()); } } };
Python 程式碼
class Solution: def nextPermutation(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ # Init min_v = 101 min_p = -1 p = -1 # Find i for i in range(len(nums)-2, -1, -1): if nums[i] < nums[i+1]: p = i # Find min_p for j in range(i, len(nums)): if nums[i] < nums[j] < min_v: min_v = nums[j] min_p = j break # Sort if p == -1: nums.sort() else: nums[i], nums[min_p] = nums[min_p], nums[i] # Bubble print(nums, i) for j in range(i+1, len(nums)-1): for k in range(i+1, len(nums)-1): if nums[k] > nums[k+1]: nums[k], nums[k+1] = nums[k+1], nums[k]