Leetcode 剑指 Offer II 084.全排列 II

题目难度: 中等

原题链接[1]

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

题目描述

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

示例 1：示例 2：提示：题目思考如何保证结果不重复?如果限制只能用递归或者迭代, 如何解决?解决方案方案 1思路复杂度代码 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思路复杂度代码 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  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

大家可以在下面这些地方找到我~

我的 [2]

我的 [3]

我的 CSDN[4]

我的知乎专栏[5]

我的头条号[6]

我的牛客网博客[7]

———END———
限 时 特 惠： 本站每日持续更新海量各大内部创业教程，永久会员只需109元，全站资源免费下载 点击查看详情
站 长 微 信： nanadh666