1. 算法简述

字典序（dictionary order），又称字母序（alphabetical order），原意是表示英文单词在字典中的先后顺序，在计算机领域中扩展成了根据不同字符的ASCII值的比较两个任意字符串的大小关系。
字典序排序算法是一种基于字典序对随机序列生成全排列的排序方法，通常用于解决这样的问题：给定其中一种排列，求基于字典序的下一种排列（要求下一种排列必须比原排列大，并且二者之间不能存在第三种排列，即下一种排列为大于原排列的最小排列）。
比如给定的排列为 afhdceb，则它的下一种排列为 afhdebc；又比如给定的排列为 5482631，则它的下一种排列为 5483126。

2. 算法的求解步骤

以上述的5482631为例，字典序排序算法的求解步骤如下：
（1）在原排列中，从右往左找出数组（序列）中第一个正序（即左边数字小于右边数字），计左边数字的下标为left，计当前左边数字为leftValue，此处left=3，leftValue=2。
（2）在原排列中，再次从右往左找出第一个比leftValue大的数，此时该数的下标记为right，此处right=5，其对应的值为3。
（3）将原排列中第left位与第right位交换（即 2 与 3 交换）后，原排列变为 5483621。
（4）将原排列从left+1到数组（序列）的末尾的数按从小到大排序，得到最小排列126，因此求得原排列的下一个排列为 5483126。

3. 基于Python的算法实现

字典序排序算法的实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def nextPermutation(nums):
    """
    :type nums: List[int]
    :rtype: List[int], next permutation
    """
    i = len(nums) - 2
    # 找到 left 的位置
    while i >= 0 and nums[i + 1] <= nums[i]:
        i -= 1

    if i >= 0:
        j = len(nums) - 1
        # 找到 right，并交换二者
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    # 将 left+1 至末尾元素升序排列
    # 由于其本身是降序，故只需反转下即可
    l, r = i + 1, len(nums) - 1
    while l < r:
        nums[l], nums[r] = nums[r], nums[l]
        l += 1
        r -= 1
    return nums

4. 算法的复杂度分析

时间复杂度：O(N)，在最坏的情况下，只需要对整个数组进行两次扫描。
空间复杂度：O(1)，没有使用额外的空间，原地替换足以做到。

• ← Previous Post
• Next Post →

...

...

00:00

00:00