leetcode47-全排列II

原题

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

示例:

输入: [1,1,2]
输出:
[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

解法

思想

这道题和leetcode46-全排列的区别在于,数组中会出现相同的数字,对于搜索来说,我们把它想象成树的DFS搜索,就应该避免在同一层搜索到相同值的节点,而不同层之间是允许存在相同值节点的。

我们使用上道题的代码进行改造,如下所示:

代码

class Solution {
    List<List<Integer>> ans = new ArrayList<>();
    int[] nums;
    public List<List<Integer>> permuteUnique(int[] nums) {
        int[] used = new int[nums.length];
        this.nums = nums;
        //要去重,先排序
        Arrays.sort(nums);
        List<Integer> list = new ArrayList<>();
        dfs(list,used,0);
        return ans;
    }
    public void dfs(List<Integer> list,int[] used,int usedCount){
        if(usedCount==nums.length){
            ans.add(list);
        }
        for(int i = 0;i<nums.length;i++){
            // i == 0,前面没有元素,可以搜索
            // used[i-1] == 0,前面的元素在别的层级用过了,可以搜索
            // nums[i]!=nums[i-1],前面的元素和当前元素不相同,可以搜索
            if(used[i]==0 && (i == 0 || used[i-1] ==1 || nums[i]!=nums[i-1])){
                List<Integer> copy = new ArrayList<>(list);
                copy.add(nums[i]);
                int[] usedCopy = Arrays.copyOf(used,used.length);
                usedCopy[i] = 1;
                dfs(copy,usedCopy,usedCount+1);
            }
        }
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode47-%e5%85%a8%e6%8e%92%e5%88%97ii/

(0)
彭晨涛彭晨涛管理者
上一篇 2020年5月9日
下一篇 2020年5月10日

相关推荐

  • leetcode328-奇偶链表

    原题 给定一个单链表,把所有的奇数节点和偶数节点分别排在一起。请注意,这里的奇数节点和偶数节点指的是节点编号的奇偶性,而不是节点的值的奇偶性。 请尝试使用原地算法完成。你的算法的空…

    算法 2019年12月16日
    0130
  • leetcode173-二叉搜索树迭代器

    原题 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。 调用 next() 将返回二叉搜索树中的下一个最小的数。 示例: BSTIterator iterator…

    2020年1月16日
    060
  • leetcode9-回文数

    原题 判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。 示例1: 输入: 121 输出: true 示例2: 输入: -121 输出: fa…

    算法 2020年2月28日
    0120
  • 剑指offer62-圆圈中最后剩下的数字

    原题(来源Leetcode) 0,1,,n-1这n个数字排成一个圆圈,从数字0开始,每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如,0、1、2、3、4这5…

    算法 2020年3月30日
    0650
  • leetcode779-第K个语法符号

    原题 在第一行我们写上一个 0。接下来的每一行,将前一行中的0替换为01,1替换为10。 给定行数 N 和序数 K,返回第 N 行中第 K个字符。(K从1开始) 例子: 输入: N…

    算法 2020年1月22日
    0110
  • leetcode27-移除元素

    原题 给定一个数组 nums 和一个值 val,你需要原地移除所有数值等于 val 的元素,返回移除后数组的新长度。 不要使用额外的数组空间,你必须在原地修改输入数组并在使用 O(…

    算法 2019年11月20日
    080
  • leetcode705-设计哈希集合

    原题 不使用任何内建的哈希表库设计一个哈希集合 具体地说,你的设计应该包含以下的功能 add(value):向哈希集合中插入一个值。 contains(value) :返回哈希集合…

    算法 2019年12月18日
    0140
  • leetcode68-文本左右对齐

    原题 https://leetcode.cn/problems/text-justification/description 解法 贪心即可 func fullJustify(wo…

    算法 2024年3月23日
    080
  • leetcode682-棒球比赛

    原题 你现在是棒球比赛记录员。给定一个字符串列表,每个字符串可以是以下四种类型之一:1. 整数(一轮的得分):直接表示您在本轮中获得的积分数。2. "+"(一轮的得…

    算法 2020年2月3日
    0210
  • leetcode101-对称二叉树

    原题 给定一个二叉树,检查它是否是镜像对称的。 例如,二叉树 [1,2,2,3,4,4,3] 是对称的。     1  &nbsp…

    算法 2020年1月11日
    0120

发表回复

登录后才能评论