31. Next Permutation

题目

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

题意与思路

题目的意思等价于：对于 一个整形数组，都对应一个数a，求由数组元素组成的数中大于a的最小数，如果不存在，则返回由这些数组元素组成的最小数
如果直接这样出，我首先想到的是暴力递归，这就等价于全排列，不过此题目给出了一种解决这种问题的思路
有这么几种情况
从数组的最后一个元素开始向前遍历(因为交换后面的元素位置得到的值要小于交换前面的元素位置得到的值)

1. 数组长度小于等于1，返回
2. 数组的最后一个元素大于倒数第二个元素
3. 第一次出现数组的第m个元素大于第m-1个元素(把第一种单独拿出来)
4. 不存在第m个元素大于第m-1个元素

设数组长度为length，数组为nums
对于第1种情况，返回
对于第2种情况，交换nums[length-1]和nums[length-2]
对于第3种情况，首先在下标为m~length-1的元素中找到大于nums[m-1]的最小元素nums[k]，交换nums[k]和nums[m-1],然后对下标为m~length-1的元素进行升序排序。
对于第4种情况，对整个数组进行升序排序
这里说到的升序排序，因为针对的时降序排序序列，只需要对应的元素进行交换即可，如 nums[m+i] 和nums[length-1-i]交换
注意：题目要求不需要返回值，要在原来的数组上修改数组

Python实现

class Solution(object):
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        length=len(nums)
        if length>1:
            i = length - 1
            nex = nums[i]
            index2=i
            i = i - 1
            flag = 0
            while i >= 0:
                if nums[i] < nex:
                    flag = 1
                    index=i
                    break
                nex=nums[i]
                i = i - 1
            if flag == 0:
                for i in range(int(len(nums) / 2)):
                    temp = nums[i]
                    nums[i] = nums[length - i - 1]
                    nums[length - i - 1] = temp
            else:
                if index2==index+1:
                    temp=nums[index2]
                    nums[index2]=nums[index]
                    nums[index]=temp
                else:
                    flag=0
                    for i in range(len(nums[index + 1:])):
                        if nums[index + 1 + i] <= nums[index]:
                            temp = nums[index]
                            nums[index] = nums[index + i]
                            nums[index + i] = temp
                            flag=1
                            break
                    if flag==0:
                        temp=nums[index]
                        nums[index]=nums[length-1]
                        nums[length-1]=temp

                    for i in range(int((index2 - index) / 2)):
                        temp = nums[index + 1 + i]
                        nums[index + 1 + i] = nums[index2 - i]
                        nums[index2 - i] = temp