Posted on 2022-11-07 04:27
Uriel 阅读(27)
评论(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