LeetCode 31. 下一个排列

题目

整数数组的一个 排列 就是将其所有成员以序列或线性顺序排列。

• 例如，arr = [1,2,3] ，以下这些都可以视作 arr 的排列：[1,2,3]、[1,3,2]、[3,1,2]、[2,3,1] 。

整数数组的下一个排列是指其整数的下一个字典序更大的排列。更正式地，如果数组的所有排列根据其字典顺序从小到大排列在一个容器中，那么数组的下一个排列就是在这个有序容器中排在它后面的那个排列。如果不存在下一个更大的排列，那么这个数组必须重排为字典序最小的排列（即，其元素按升序排列）。

• 例如，arr = [1,2,3] 的下一个排列是 [1,3,2] 。
• 类似地，arr = [2,3,1] 的下一个排列是 [3,1,2] 。
• 而 arr = [3,2,1] 的下一个排列是 [1,2,3] ，因为 [3,2,1] 不存在一个字典序更大的排列。

给你一个整数数组 nums ，找出 nums 的下一个排列。必须原地修改，只允许使用额外常数空间。

例：
输入：nums = [1,2,3]
输出：[1,3,2]

方法

根据题目求整数数组的下一个排列，若将此时的数组看成一个数，下一个排列应使该数的增幅尽可能的小，那么在使得前面的小数与后面的大数进行交换时，小数应尽可能的靠后，大数应尽可能的小。在交换完成后，以升序排列大数后的数字即可

• i 记录小数的下标，j 记录小数的后一个数的下标。从后向前查找第一组相邻并且升序的元素对 (i, j)，满足 nums[i] < num[j]，那么 [j, end] 的数字为降序
• k 记录尽可能小的大数。从后向前在范围 [j, end] 内寻找，并且该数应大于 nums[i]
• 若此时数组存在下一个更大的排列，那么交换 nums[i] 和 nums[k]，并且对 [j, end] 的数字进行升序排列
• 若此时数组不存在下一个更大的排列，那么根据题目，将其变成最小的排列

class Solution(object):
    def nextPermutation(self, nums):
        if len(nums) == 1:
            return

        i, j, k = len(nums)-2, len(nums)-1, len(nums)-1
        while i >= 0 and nums[i] >= nums[j]:
            i -= 1
            j -= 1
        while k > j and nums[k] <= nums[i]:
            k -= 1
        if i != -1:
            nums[i], nums[k] = nums[k], nums[i]
            nums[:] = nums[:j] + nums[j:][::-1]
        else:
            nums[:] = nums[::-1]

例：12385764
第一步：i = 4， j = 5， nums[i] = 5 <= nums[j] = 7，[j, end] = [7, 6, 4] 为降序排列
第二步：k = 6，nums[k] = 6 > nums[i] = 5
第三步：12386754，对 5 和 6 的位置进行交换
第四步：排列，最终结果 12386457

相关知识

• 切片：
  

参考

代码相关：https://leetcode.cn/problems/next-permutation/solution/xia-yi-ge-pai-lie-suan-fa-xiang-jie-si-lu-tui-dao-/
切片：https://blog.csdn.net/m0_54923920/article/details/124957695