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()  # 重新从小到大排序