当前位置:网站首页>LeetCode 47. 全排列 II

LeetCode 47. 全排列 II

2021-10-14 03:22:51 数据结构和算法

截止到目前我已经写了 600多道算法题,其中部分已经整理成了pdf文档,目前总共有1000多页(并且还会不断的增加),大家可以免费下载
下载链接https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码:6666

在这里插入图片描述
这题和前面讲的593,经典回溯算法题-全排列差不多,不过这题有重复数字,但593题没有重复数字。有重复的数字肯定就会有重复的组合,所以这题需要过滤掉重复的组合。如果不过滤会有什么结果,我们以示例一为例来个图来看一下(这里为了区分第一个1和第二个1,我分别用了黑色和红色标记)。

在这里插入图片描述

怎么样才能过滤掉重复的数字呢,一种方式就是找出所有的组合结果,然后在这个结果中过滤掉重复的组合。如果组合是字符串还好比较,但这里是个数组,所有数组两两比较复杂度太高,这种方式我们不考虑。


除了上面说的一种解法还有一种方式就是我们常说的剪枝,怎么剪呢?因为要过滤掉重复的,只有重复的数字才会造成重复的结果。所以第一步要做的就是对数组进行排序,排序之后相同的数字肯定是挨着的。


当遍历到当前数字的时候,如果数组中当前数字和前一个数字一样,并且前一个数字没有被使用,我们就跳过当前分支,也就是把当前分支给剪掉。如下图所示

在这里插入图片描述

代码如下

public List<List<Integer>> permuteUnique(int[] nums) {
    
    //先对数组进行排序,这样做目的是相同的值在数组中肯定是挨着的,
    //方便过滤掉重复的结果
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //boolean数组,used[i]表示元素nums[i]是否被访问过
    boolean[] used = new boolean[nums.length];
    //执行回溯算法
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    
    //如果数组中的所有元素都使用完了,类似于到了叶子节点,
    //我们直接把从根节点到当前叶子节点这条路径的元素加入
    //到集合res中
    if (tempList.size() == nums.length) {
    
        res.add(new ArrayList<>(tempList));
        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;
        //否则我们就使用当前元素,把他标记为已使用
        used[i] = true;
        //把当前元素nums[i]添加到tempList中
        tempList.add(nums[i]);
        //递归,类似于n叉树的遍历,继续往下走
        backtrack(nums, used, tempList, res);
        //递归完之后会往回走,往回走的时候要撤销选择
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}

除了上面说的剪枝方式,还有没有其他的剪枝方式呢,实际上是有的。就是当遍历到当前数字的时候,如果当前数字和数组中前一个数字一样,并且前一个数字被使用了,我们就跳过当前分支,也就是把当前分支给剪掉(和上面的相反)。如下图所示

在这里插入图片描述
这就是前面我们在讲590,回溯算法解正方形数组的数目中最后提到的,这两种剪枝方式都是可以的,一种是把整个大枝剪掉,一种是在每个大枝下面不停的剪小枝。很明显第一种剪枝效率更高一些,我们来看下代码

public List<List<Integer>> permuteUnique(int[] nums) {
    
    //先对数组进行排序,这样做目的是相同的值在数组中肯定是挨着的,
    //方便过滤掉重复的结果
    Arrays.sort(nums);
    List<List<Integer>> res = new ArrayList<>();
    //boolean数组,used[i]表示元素nums[i]是否被访问过
    boolean[] used = new boolean[nums.length];
    //执行回溯算法
    backtrack(nums, used, new ArrayList<>(), res);
    return res;
}

public void backtrack(int[] nums, boolean[] used, List<Integer> tempList, List<List<Integer>> res) {
    
    //如果数组中的所有元素都使用完了,类似于到了叶子节点,
    //我们直接把从根节点到当前叶子节点这条路径的元素加入
    //到集合res中
    if (tempList.size() == nums.length) {
    
        res.add(new ArrayList<>(tempList));
        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;
        //否则我们就使用当前元素,把他标记为已使用
        used[i] = true;
        //把当前元素nums[i]添加到tempList中
        tempList.add(nums[i]);
        //递归,类似于n叉树的遍历,继续往下走
        backtrack(nums, used, tempList, res);
        //递归完之后会往回走,往回走的时候要撤销选择
        used[i] = false;
        tempList.remove(tempList.size() - 1);
    }
}

上面两种代码非常相似,唯一不同的就是下面这行,其他的都一样。

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

如果让我们选择的话,我们肯定会选择第一种方式,把整个大的枝给剪掉。

版权声明
本文为[数据结构和算法]所创,转载请带上原文链接,感谢
https://blog.csdn.net/abcdef314159/article/details/120738739

随机推荐