LeetCode解题报告(31)--数字排列的下一项

发表于 标签

原题如下： >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, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

题目的意思就是对给出的数字list进行排列组合并从小到大排序，找出给出的list组成的数字的下一个数。

实现的时候当然不会弄得像上面说的这么复杂，只需要对给出的list从后往前遍历，找到第一个当前数字(记为i)比前一数字(记为j)大的那个数字，然后从这个位置往后的数字中找到一个>j&&<=i的最小的数字，交换两者后再对i后面的数字排序即可，说起来比较拗口。下面举个简单的例子。

假如给出的list是[1,2,5,4,3],找到的i=5，j=2,然后将i后面大于j且小于等于i的最小数字与j交换，这里是3，也就是交换后的list是[1,3,5,4,2],然后对i后面的数字进行排序，排序后为[1,3,2,4,5]，也是我们得到的结果。

实现代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#encoding:utf-8
class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """  
        i = len(nums)-1
        flag = 0
        while i > 0:
            if nums[i] > nums[i-1]:
                # 往后找大于nums[i-1]且小于nums[i]的数与nums[i-1]交换
                j = len(nums)-1
                while j>i:
                    if nums[i-1]<nums[j]<nums[i]:
                        nums[j],nums[i-1] = nums[i-1],nums[j]
                        flag = 1
                        break
                    j-=1
                        
                # 找不到这样的数
                if flag == 0:
                    nums[i],nums[i-1] = nums[i-1],nums[i]
                
                # 交换后对i后面的元素进行排序
                nums[i:] = sorted(nums[i:])
                return                 
            else:
                i-=1
        nums.sort()  # 重新从小到大排序