每天一题LeetCode【第34天】

T47. Permutations II【Medium】

题目

给出一个可以包含重复数字的数字集，返回所有可能的不重复排列组合。

例如，
[1,1,2] 有如下的排列组合：

[
  [1,1,2],
  [1,2,1],
  [2,1,1]
]

思路

这题的大体想法和上题一样，不过除了递归，这题还要对重复怎么判断进行处理，以及防止重复排列组合的出现。

① 递归

思路和上一题差不多，如下：

排列组合（1 2 3）
= 1 + 排列组合（2 3）∪ 2 + 排列组合（1 3）∪ 3 + 排列组合（1 2）
排列组合（2 3）
= 2 + 排列组合（3）∪ 3 + 排列组合（2）
= 23 ∪ 32 

可以看出在数字只有一个的时候到了递归的终点

② 重复判别

上一题是直接看这个数有没有用过，那是基于这个数只出现一遍，而在这题可以出现重复的数字这个方法就不可用了。这个 Solution 用了什么解决方法呢，看下面：

boolean[] used = new boolean[nums.length];

建立了一个 boolean 的数组和 nums 中的数一一对应,然后用

used[i]=true;
used[i]=false;

的设置来表示这个数是否用过

然后用在循环中加入下面的语句来跳过用过的数字

if(used[i]) continue;

③ 排除重复排列组合

造成重复排列组合的原因可以动手写一下看看~

避免这种重复的方法在于后面重复的数不能排在前面重复的数前面（可能有点绕，最好动手写写看）。

代码则是很简单，像下面这样：

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

因为已经排好序了，所以若 nums[i-1]==nums[i] 和 !used[i-1] 则代表它之前的重复的数没有被用到，这时，跳过这次循环，因为它也不应该被用。

另外，不能写成

if(i>0 &nums[i-1]==nums[i] & !used[i-1]) continue;

可以想一下原因~我在补充里说！

代码

代码取自 Top Solution，稍作注释

public List<List<Integer>> permuteUnique(int[] nums) {
        //建立要返回的数据形式
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        //若为空,直接返回
        if(nums==null || nums.length==0) return res;
        //建立 used 数组来判断这个数字是否用过
        boolean[] used = new boolean[nums.length];
        List<Integer> list = new ArrayList<Integer>();
        //排序
        Arrays.sort(nums);
        dfs(nums, used, list, res);
        return res;
    }

public void dfs(int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res){
        //若所有元素都用到了(达到长度)则加到 ArrayList 里面
        if(list.size()==nums.length){
            res.add(new ArrayList<Integer>(list));
            return;
        }
        for(int i=0;i<nums.length;i++){
            //若用到过这个数字了,则跳过本次循环
            if(used[i]) continue;
            //用这句来避免重复
            if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;
            //设置为true代表已经用过
            used[i]=true;
            //下面四行是递归,看和上一题差不多,看"思路"里
            list.add(nums[i]);
            dfs(nums,used,list,res);
            used[i]=false;
            list.remove(list.size()-1);
        }
    } 

补充

关于

if(i>0 &&nums[i-1]==nums[i] && !used[i-1]) continue;

为什么要用 "&&" 而不用 "&"?

我们可以尝试先把 "&&" 改成 "&"，然后发现会报错！

为什么呢？我的编译器不爱我了吗？

这要先讲一下两者的区别：

&&和&都是表示与，区别是&&只要第一个条件不满足，后面条件就不再判断。而&要对所有的条件都进行判断。

因为当用了 && 时，执行 i>0 为 false 时就不往下执行了，而用 & 时会把这三个都执行一遍，在执行

nums[i-1]==nums[i]

的时候 nums[i-1] 是 nums[-1],会报 ArrayIndexOutOfBoundsException 的错误。