31. 下一个排列 #

问题描述#

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

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

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

示例 1：
输入：nums = [1,2,3]
输出：[1,3,2]
示例 2：
输入：nums = [3,2,1]
输出：[1,2,3]
示例 3：
输入：nums = [1,1,5]
输出：[1,5,1]
示例 4：
输入：nums = [1]
输出：[1]
提示：

1 <= nums.length <= 100

0 <= nums[i] <= 100

解题思路#

从后往前，对于当前位置的数，从其后的数中找到比该数大的所有数中的最小数，将找到的数与当前位置的数进行交换，并对当前位置的数之后的数进行排序。找到第一次满足该条件的数即可。

from bisect import bisect
from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)

        for i in range(n - 2, -1, -1):
            k = bisect(nums[i + 1 :], nums[i]) # 当前位置之后的数已经有序
            if k == n - i - 1: # 该数比之后的数都大
                # 将该数移动到最后面，使包括当前位置的数在内的数重新变得有序
                t = nums[i]
                for j in range(i, n - 1):
                    nums[j] = nums[j + 1]
                nums[-1] = t
            else:
                nums[i], nums[k + i + 1] = nums[k + i + 1], nums[i]
                break

from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i == -1:  # 非增序列
            nums.reverse()
            return

        # 显然 nums[i+1:n] 是个递减序列（非增序列）
        # 使用二分法找到 nums[i+1:n] 中比 nums[i] 大的最小数 
        lo, hi = i + 1, n - 1
        while lo < hi:
            mid = (lo + hi) // 2
            if nums[mid] <= nums[i]:
                hi = mid - 1
            else:
                lo = mid
                if nums[lo + 1] > nums[i]:
                    lo += 1
                else:
                    break
        # 交换该数到位置 i
        nums[i], nums[lo] = nums[lo], nums[i]

        # 对 nums[i+1:] 升序排列
        lo, hi = i + 1, n - 1
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo, hi = lo + 1, hi - 1

31. 下一个排列#

问题描述#

解题思路#

31. 下一个排列 #