Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给一列数,生成下一个排列数
从最后一个数字向前扫,找到最长的升序后缀,升序后缀前一位和升序后缀第一位大于该数的数字交换,然后升序列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 

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理