题目描述

实现获取下一个排列的函数，算法需要将给定数字序列重新排列成字典序中下一个更大的排列。

如果不存在下一个更大的排列，则将数字重新排列成最小的排列（即升序排列）。

必须原地修改，只允许使用额外常数空间。

以下是一些例子，输入位于左侧列，其相应输出位于右侧列。 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5 → 1,5,1

我的解法——数组转置+变量交换（AC）

如果想要找到下一个排列
- 找到递增的位置是关键，因为在这里才可以使其增长得更大。
- 然后将后面递减的有序数组转置成递增的。
- 然后找出比这个数大但在这些大数里面最小的值，并将其两者调换。
复杂度O(n)
Beat64%

class Solution:
    def nextPermutation(self, nums):
        """
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        """
        flag = False
        length = len(nums)
        
        for i in range(length - 1,0,-1):
            if(nums[i] > nums[i - 1]):
                for j in range(int((length - i)/2)):
                    nums[i + j],nums[length - 1 - j] = nums[length - 1 - j],nums[i + j]
                for j in range(length - i):
                    if(nums[i + j] > nums[i - 1]):
                        nums[i + j],nums[i - 1] = nums[i - 1],nums[i + j]
                        break
                flag = True
                break
        if(not flag):
            nums.sort()