欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

python算法(输入一个包含重复数字的序列返回不重复的全排列)

程序员文章站 2022-06-20 13:05:53
1、题目描述https://leetcode-cn.com/problems/permutations-ii/给定一个可包含重复数字的序列,返回所有不重复的全排列。2、代码详解相关题:回溯-LeetCode46. 全排列(不重复的数字)https://blog.csdn.net/IOT_victor/article/details/107072205加入 nums[i] == nums[i-1] 判断nums.sort()class Solution(object): .....

1、题目描述

给定一个可包含重复数字的序列,返回所有不重复的全排列。

python算法(输入一个包含重复数字的序列返回不重复的全排列)

2、代码详解 

  1. 加入 nums[i] == nums[i-1] 判断
  2. nums.sort()
class Solution(object):
    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # nums 选择列表,depth深度, path 路径,used 标记数组!,res 结果
        def dfs(nums, size, depth, path, used, res):
            # 结束条件:nums 中的元素全都在 path 中出现
            if depth == size:
                res.append(path[:])  # 需要传递下path的拷贝,否则对path的修改会影响到结果
                return

            for i in range(size):
                # used[i]==False,表示未被用过
                if not used[i]:
                    # (新加判重)剪枝!!!
                    # 如果出现连续重复的字符,跳出for循环(必须操作,用例1,1,不然会输出["1,1","1,1"])
                    # 加上not used[i-1],这样的剪枝更彻底,不加也能通过
                    if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
                        continue
                    # 做选择
                    used[i] = True
                    path.append(nums[i])

                    # 进入下一层决策树
                    dfs(nums, size, depth + 1, path, used, res)

                    # 撤销选择
                    used[i] = False
                    path.pop()

        size = len(nums)
        if len(nums) == 0:
            return []

        # (排序)在搜索之前就对候选数组排序
        # 一旦发现这一支搜索下去可能搜索到重复的元素就停止搜索,这样结果集中不会包含重复元素
        nums.sort()

        used = [False for _ in range(size)]
        res = []
        dfs(nums, size, 0, [], used, res)
        return res

nums = [1,1,2]
s = Solution()
print(s.permuteUnique(nums)) 

本文地址:https://blog.csdn.net/IOT_victor/article/details/107073704