Posted on 2022-11-07 04:27
Uriel 閱讀(63)
評論(0) 編輯 收藏 引用 所屬分類:
數學 、
閑來無事重切Leet Code
給一列數，生成下一個排列數
從最后一個數字向前掃，找到最長的升序后綴，升序后綴前一位和升序后綴第一位大于該數的數字交換，然后升序列reverse
舉例：
1 2 5 3 3 0
升序后綴的前一位為2，升序后綴第一個大于2的數為3，交換兩個數，得到
1 3 5 3 2 0
reverse升序后綴
1 3 0 2 3 5
如果已經是最后一個排列數，如
5 4 3 2 1
則不存在前一位，直接reverse
1 #31
2 #Runtime: 53 ms
3 #Memory Usage: 13.3 MB
4
5 class Solution(object):
6 def nextPermutation(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: None Do not return anything, modify nums in-place instead.
10 """
11 f = -1
12 for i in range(len(nums)-2, -1, -1):
13 if nums[i] < nums[i + 1]:
14 f = i
15 break
16 if f >= 0:
17 for i in range(len(nums)-1, -1, -1):
18 if nums[i] > nums[f]:
19 nums[f], nums[i] = nums[i], nums[f]
20 break
21 nums[f + 1 : ] = nums[f + 1 : ][ : : -1]
22 return nums
23