LEETCODE 47. Permutations II 解题思路分析

题目大意:

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

示例:

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=47

解题思路分析:

本题的本质实际上是将数组中的每一个元素都看作是一个节点,然后以每个节点作为起点dfs递归所有路径。不过本题与前一题相比,存在重复数字,这会导致不同的dfs路径存在相同的结果,比如数组[1,1,1],虽然存在多条dfs路径,但是结果都是相同的。因此,解题时,我们需要先将数组排序,然后在dfs选择节点时,当前所有没有选择过的节点都是我们可以选择的路径(分叉),但是为了避免重复,这些节点中数值相同的节点只能选择一次。

如果你并不熟悉dfs深度优先搜索算法,建议你先参考一下我之前讲过的文章:

LEETCODE常见算法之深度优先搜索DFS超详细白话讲解(上)

实现代码:

List<List<Integer>> res = new ArrayList<>();
public List<List<Integer>> permuteUnique(int[] nums) {
    Arrays.sort(nums);
    dfs(nums, new ArrayList<>(),new boolean[nums.length]);
    return res;
}
void dfs(int[] nums, List<Integer> list, boolean[] visited){
    if(list.size()==nums.length){
        res.add(new ArrayList<>(list));
        return;
    }
    for(int i=0;i<nums.length;i++){
        if(visited[i]) continue;
        if(i>0&&nums[i]==nums[i-1]&&!visited[i-1]) continue;
        visited[i]=true;
        list.add(nums[i]);
        dfs(nums,list,visited);
        visited[i]=false;
        list.remove(list.size()-1);
    }
}

本题解法执行时间为1ms。

Runtime: 1 ms, faster than 99.41% of Java online submissions for Permutations II.

Memory Usage: 40.5 MB, less than 34.33% of Java online submissions for Permutations II.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: https://leetcode.jp/leetcode-47-permutations-ii-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。