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