Leetcode31下一个排列

31下一个排列

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

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/next-permutation 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Solution 1

下一个排列等于，从后往前找不满足升序的元素，将它变大一点（与后面的元素交换位置），然后将它之后的元素排序
时间复杂度：O(n)
空间复杂度：O(1)
执行用时：44 ms
内存消耗：13.7 MB

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        i = len(nums)-1
        # 找从后往前不满足升序的数
        while (i > 0):
            if (nums[i] <= nums[i-1]):
                i -= 1
            else:
                break
        # 全部满足从后往前升序
        if (i == 0):
            # 之后将那个数之后的素组排列为从前往后升序
            j = len(nums)-1
            while(i < j):
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                i += 1
                j -= 1
        else:
            # 将不满足升序的数变大一点
            temp = nums[i-1]
            # 找刚好比nums[i-1]大一点的数
            j = i
            while(j < len(nums)):
                if (nums[j] > temp):
                    j += 1
                else:
                    break
            # 交换
            nums[i-1] = nums[j-1]
            nums[j-1] = temp
            # 之后将那个数之后的素组排列为从前往后升序
            j = len(nums)-1
            while(i < j):
                temp = nums[i]
                nums[i] = nums[j]
                nums[j] = temp
                i += 1
                j -= 1