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]，也是我们得到的结果。

实现代码如下：

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