******** 剑指 Offer II 084.全排列 II

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer（专项突击版）系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

给定一个可包含重复数字的整数集合 nums ，按任意顺序返回它所有不重复的全排列。

示例 1：

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

示例 2：

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

提示：

1 <= nums.length <= 8
-10 <= nums[i] <= 10

题目思考

如何保证结果不重复?
如果限制只能用递归或者迭代, 如何解决?

解决方案

方案 1

思路

分析题目, 不难发现这道题和上一道题(剑指 Offer II 083.全排列)非常类似, 区别只是数字存在重复, 那能否继续使用之前的做法呢?
对于之前的方案 1 递归做法, 由于现在有了重复数字, 那么最终形成的排列也可能重复
例如[1,3,1], 假设两个 1 分别叫 a1 和 b1, 那么 a1->b1->3 和 b1->a1->3 形成的排列就会重复, 都是[1,1,3]
所以如果继续用递归, 那么需要将形成的排列转成元组 (Python 的列表不能作为集合或字典的 key), 然后添加到集合中去重, 最终再转成列表返回, 这样会增加一些时间复杂度, 不是很推荐, 有没有更好的做法呢?
既然在不同位置选择相同的数字会导致重复, 那么我们可以将相同数字聚合起来, 对应的就是计数字典{key:cnt}
然后针对字典的每个 key, 只要它的计数仍大于 0, 就可以使用它, 我们不关心使用的是具体哪个位置的数字
这样就自动做到了去重, 针对上面的例子, 如果连着用两次 1, 那么只会产生一个排列, 就是[1,1,3]
其余部分就和上一道题非常类似了, 本质上来说, 上一道题相当于这道题的特例, 每个数字都形成了计数为 1 的计数字典
我们可以基于上述分析进行递归求解, 具体做法如下:
1. 将原始数组转换成计数字典
2. 针对计数字典的每个 key, 逐一遍历它们
3. 如果当前 key 的计数大于 0, 则可以使用它, 将其计数减 1 并追加到当前排列中, 然后继续递归
4. 当前 key 的递归结束后, 需要将计数加 1, 恢复到原始状态, 代表这次先不使用它, 而是继续遍历下一个 key
5. 最后当得到的排列的长度等于原始数组长度时结束递归, 此时就形成了一个有效且不重复的排列
下面的代码中有详细的注释, 方便大家理解

复杂度

时间复杂度 O(N!): 最差情况下 N 个数字各不相同, 排列就有 N! 种
空间复杂度 O(N): 计数字典和 key 列表需要存储最多 N 个元素, 而递归栈在最差情况下长度同样是 N

代码

Python 3

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 方法1: 计数字典+dfs(perm)
        res = []
        # 将原始数组转换成计数字典
        cnts = collections.Counter(nums)

        def dfs(perm):
            if len(perm) == len(nums):
                # 当前排列长度等于原始数组长度, 将其加入最终结果中
                res.append(perm)
                return
            for key in cnts:
                if cnts[key] > 0:
                    # 当前key的计数大于0, 可以追加到排列中
                    # 先尝试追加当前key, 将其计数减1并追加到当前排列中
                    cnts[key] -= 1
                    dfs(perm + [key])
                    # 将其计数恢复, 代表暂不追加当前key
                    cnts[key] += 1

        # 初始排列是空的, 在递归过程中会逐步往里面加数字
        dfs([])
        return res

方案 2

思路

接下来我们尝试用迭代的思路来解决, 对于剑指 Offer II 083.全排列的方案 2 迭代做法, 由于每次新的排列都是大于当前排列且最接近它的, 所有排列依次递增, 这样天然做到了去重, 所以我们直接可以复用它
这里我把相同的思路贴过来了, 方便大家参考
我们可以定义一个方法, 来求按顺序的下一个排列, 例如[1,2,3]->[1,3,2]->[2,1,3]->[2,3,1]->[3,1,2]->[3,2,1], 这样就能保证得到每个不重复的排列
先将给定数组按升序排序, 然后当遍历到的排列变成降序排序的时候, 就说明所有排列都被找到了
所以算法的核心就是如何通过一个排列找它按顺序的下一个排列
下一个排列一定是所有排列中大于当前排列且最接近它的, 所以我们可以利用贪心算法, 具体步骤如下:
1. 从后向前找第一个小于后一个数字的下标 i (因为如果大于等于后一个数字的话, 就没法与后面的数字交换来使得整体排列更大了)
2. 找刚才遍历的部分的大于且最接近下标 i 对应数字的下标 j
3. 将它们两个互换
4. 然后 i 往后的部分都按升序排列, 也即将这部分逆序 (因为现在这部分是降序排序的)
这样就保证了新的排列一定是大于当前排列且最接近它的, 不可能有更小的了
下面的代码中有详细的注释, 方便大家理解

复杂度

时间复杂度 O(N*N!): N 个数字各不相同, 排列就有 N! 种, 从当前排列转入下一个排列需要 O(N) 时间
空间复杂度 O(1): 只使用了几个常数空间的变量 (不考虑输出结果集)

代码

Python 3

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        # 方法2: 迭代getNext
        res = []
        n = len(nums)

        def getNext(nums):
            for i in range(n - 1)[::-1]:
                # 从后向前查找
                if nums[i] < nums[i + 1]:
                    # 找到目标数字了, 接下来找后面部分中大于nums[i]且最接近它的数字
                    j = i + 1
                    while j < n and nums[j] > nums[i]:
                        j += 1
                    # 此时nums[j]<=nums[i], 将它减1后的nums[j]就是后面部分中大于nums[i]且最接近它的数字, 它需要和nums[i]互换
                    j -= 1
                    # 单独拿出新的右边部分(已经将下标i和j互换了), 肯定严格按照降序排列
                    right = nums[i + 1 : j] + [nums[i]] + nums[j + 1 :]
                    # 将三部分拼接起来, 注意右边部分要逆序, 这样就变成升序排列
                    return nums[:i] + [nums[j]] + right[::-1]
            # 没找到下一个排列, 说明当前排列就是顺序最大的了, 直接返回None
            return None

        # 先拿到顺序最小的排列
        nums.sort()
        while nums:
            res.append(nums)
            nums = getNext(nums)
        return res