友链
姚屹晨

leetcode - [47] Permutations II

2020/06/18

题目描述

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

统计一个包含重复元素数组的排列情况。

举个例子：

类似题目：

[46] Permutations

Update at 2020_0907

重新梳理一下，重点在于如何处理重复的元素。

首先，我们需要对原始数组进行排序。

然后，我们还需要一个布尔数组来确认已用和未用的元素，

在DFS遍历时，若发现以下两种情况时，则跳过当前元素：

第一种： 当前元素已经使用过，也就是used[i] == true。

第二种： 当前元素与前一个元素相等，且前一个元素尚未被使用，即

i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false

来看下示意图：

再来看下完整实现：

class Solution {

    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] nums, LinkedList<Integer> child, int u, boolean[] used){

        if (child.size() == nums.length){
            ans.add(new LinkedList<>(child));
            return;
        }

        for (int i = 0; i < nums.length; i++){
            if (used[i] || i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
            used[i] = true;
            child.add(nums[i]);
            dfs(nums, child, u + 1, used);
            child.removeLast();
            used[i] = false;
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        var used = new boolean[n];
        dfs(nums, new LinkedList<>(), 0, used);
        return ans;
    }
}

Update at 2020_0825

首先，我们需要对原始数组进行排序，对于重复的元素，我们只要保证它们之间的先后顺序即可。

也就是说，如果当前元素nums[i]还没用过，且它与前一个元素相等nums[i] == nums[i - 1]，

那么就要保证第i - 1个元素一定是用过的，否则跳过。

class Solution {

    boolean[] used;
    LinkedList<Integer> child = new LinkedList<>();
    List<List<Integer>> ans = new LinkedList<>();

    private void dfs(int[] nums, int u){
        int n = nums.length;
        if (u == n){
            ans.add(new LinkedList<>(child));
            return;
        }
        for (int i = 0; i < n; i++){
            // 当前元素若已使用过，则直接跳过
            if (!used[i]){
                // 说明前面一个重复的元素还没有使用
                if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) continue;
                used[i] = true;
                child.add(nums[i]);
                dfs(nums, u + 1);
                child.removeLast();
                used[i] = false;
            }
        }
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        int n = nums.length;
        if (n == 0) return ans;
        used = new boolean[n];
        // 记得排序
        Arrays.sort(nums);
        dfs(nums, 0);
        return ans;
    }
}

解法1

Thanks @issac3

此乃神人也。

这道题目的原始数组就算只有三个元素[1, 1, 2]，包含的流程也极其复杂，

仅最外层i = 0的情况，就画了我整整一张A4纸，所以这道题，就不上示意图了，若有兴趣，可以自己画画。

来说下关键点。

关键点还是如何避免添加重复的集合，比如[1, 1, 2]和[1, 1, 2]。

于是，@issac3 借助了一个布尔数组，一旦用了当前索引就将其设置为true，

当相应递归结束后，再将其还原为false。

再来明确下跳过当前元素的条件：

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

说实话，没有参透背后的原理。

来看下实现：

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        
        Arrays.sort(nums);
        List<List<Integer>> ans = new LinkedList<>();
        bt(nums, ans, new LinkedList<>(), new boolean[nums.length]);
        return ans;
    }
    
    private void bt(int[] nums, List<List<Integer>> ans, LinkedList<Integer> child, boolean[] used){
        
        int len = nums.length;
        if (child.size() == len){
            ans.add(new LinkedList<>(child));
        } else {
            for (int i = 0; i < len; i++){
                boolean cond = i > 0 && nums[i] == nums[i - 1] && !used[i - 1];
                if (used[i] || cond) continue;
                child.add(nums[i]);
                used[i] = true;
                bt(nums, ans, child, used);
                used[i] = false;
                child.removeLast();
            }
        }
    }
}

Enjoy it!


一位喜欢提问、尝试的程序员

（转载本站文章请注明作者和出处 姚屹晨-yaoyichen）

Post Directory