46b257e48ee1d7ccf69793cbd45008e9
(难度Medium) Problem 31. Next Permutation(下一个组合)

链接

https://leetcode.com/problems/next-permutation/solution/

难度等级

Medium

题干

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place and use only constant extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题意

题意不难理解,C++当中有一个系统函数叫做next_permutation。用来生成下一个字典序的排列。

比如1,2,3这三个元素,所有的排列组合一共有6种,按照字典序排列是如下的顺序:

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

使用next_permutation传入一个数组,自动调整元素顺序,生成下一个排列。比如输入1 2 3 返回1 3 2,输入2 1 3 返回 2 3 1

样例

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

题解

解法一: 暴力枚举

我们当然可以暴力枚举所有的排列组合,然后记录下满足要求的最小的字典序。

排列组合的暴力枚举通常采用回溯的方式实现,和经典的问题八皇后类似。

def brute_force(arr, ele, nums):
    # 当所有元素都已经放入arr
    if ele is None:
        # 判断是否合法,并且是最小的
        if arr > nums and arr < mini:
            mini = arr
    # 如果还有元素没有放入
    for i in ele:
        # 因为每次放入元素都会从备选当中移除,所以可以不用判断
        arr.append(i)
        ele.remove(i)
        brute_force(arr, ele)
        ele.append(i)

这么做的复杂度也不难想象,即使不考虑判断组合是否合法的消耗,至少也是$O(n!)$级的。显然这种复杂度是不能接受的。

解法二: 贪心

top Created with Sketch.