题目描述

[EN | CN]

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

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

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

以下是一些例子,输入位于左侧列,其相应输出位于右侧列。

  • 1,2,31,3,2
  • 3,2,11,2,3
  • 1,1,51,5,1

解法 1:直接法

首先我们要明白 字典序全排列 的规则。对于某个字符串而言:

  • 如果最后的 k 个字符是升序的,那么只需要简单调换即可,例如从 12 变成 21
  • 如果最后的 k 个字符是降序的,我们往前找直到找到一个非降序的字符(假设这里为倒数第 k+1 个字符),例如 2431,那么我们将该序列的 2 与降序序列中比 2 大的最小值 3 交换得到 3421,然后将该降序序列排序得到 3124,这里的排序可以 用简单的冒泡排序遍历一遍为降序序列,然后转一下顺序 即可;
  • 如果整个字符串都是降序的,那么返回字典序的第一个排列,即所有字符从小到大排序。

举个具体例子:假如我们需要找到 124653 的下一个排列,那么我们扫描:

  1. 从右往左扫描,看是否是递减的,然后发现最后 3 位 653 是递减的,再看下一个数字的时候 4653 不是递减的,此时我们应该找 4653 的下一个排列,然后与前面的 12 拼接;
  2. 对于 4653 的下一个排列,我们找到大于 4 的最小数字,即 5,然后交换他们得到 5643
  3. 然后将原降序序列的几个字符从小到大排序,获得 5346
  4. 将获得的结果与前面的 12 拼接,作为最后返回的结果。

假设数组长度为 $n$,那么

  • 时间复杂度为 $O(n)$,虽然里面我们用到了排序,但本题中待排序的数组是基本排好序的数组的,因此排序是非常简单的 $O(n)$ 复杂度,最坏情况下本题一共需要扫描 2 遍;
  • 空间复杂度为 $O(1)$,常数空间。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        s = -1
        for i in range(len(nums) - 1, 0, -1):
            if nums[i - 1] < nums[i]:
                s = i - 1
                break
        if s != -1:
            for i in range(len(nums) - 1, s, -1):
                if nums[i] > nums[s]:
                    nums[i], nums[s] = nums[s], nums[i]
                    break
        nums[s + 1:] = nums[s + 1:][::-1]
  • 执行用时:44 ms,在所有 Python3 提交中击败了 58.52% 的用户。
  • 内存消耗:13.6 MB,在所有 Python3 提交中击败了 8.33% 的用户。