Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

 123 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1 

Related Topics: Array

解題邏輯與實作

[1, 9, 2, 5, 4, 1]
[1, 9, 2, 5, 4, 1]
[1, 9, 4, 5, 2, 1]
[1, 9, 4, 5, 2, 1]
[1, 9, 4, 1, 2, 5]

1. 由後向前搜尋找到第一個降序的點，其 index 為 i，若無則，將整個數列反轉後回傳
2. 找到 index 為 i 降序點右側第一個大於降序點的值，並與降序點交換
3. 將 index 為 i 的右側進行降序排列。
 1234567891011121314151617181920212223242526272829303132333435 class Solution: def nextPermutation(self, nums): """ :type nums: List[int] :rtype: void Do not return anything, modify nums in-place instead. """ descending_idx = self.find_descending_point(nums) if descending_idx == -1 : nums.reverse() return swap_idx = self.find_more_than(nums,descending_idx) nums[swap_idx], nums[descending_idx]= nums[descending_idx], nums[swap_idx] nums[descending_idx+1:] = sorted(nums[descending_idx+1:]) def find_more_than(self, nums, target_indx): result_indx = -1 for i in range(target_indx+1,len(nums),1): if nums[i] > nums[target_indx] and (result_indx ==-1 or nums[i] < nums[result_indx]): result_indx = i return result_indx def find_descending_point(self, nums): point = -1 for i in range(len(nums)-1,0,-1): if nums[i] > nums[i-1] : point = i-1 break return point