首页 > 代码库 > LeetCode Permutations II
LeetCode Permutations II
题目
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
For example,[1,1,2]
have the following unique permutations:[1,1,2]
, [1,2,1]
, and [2,1,1]
.
思路分析:Permutation的题目都可以formalize成Search问题来解,当我们把数组排序后,可以从空集开始,不断添加没有使用过的数字形成新的set,直到这个set的长度等于num数组的长度那么就找到了一个Permutation。用DFS搜索解比较直接。但是这题要注意判断重复数字的情况,对于排序后的数组从前向后迭代,重复数字肯定是相邻数字,那么如果当前数字等于前一个相邻数字而前一个数字没有使用,说明添加这个数字到尾部所形成的分支已经在之前搜索过,不必再搜索一次,可以剪掉,直接返回。为了深入理解这个DFS搜索的过程,我画出了针对两个简单输入例子的搜索树。给出了没有重复数字(1 2 3)和有重复数字(1 1 2)针对Permutation的搜索过程。另外,这题还要注意向结果List中添加新的Permutation时要添加拷贝而不是原来的对象引用,否则后面对state的操作会覆盖之前添加的Permutation,这是很容易犯的的错误,要特别小心。
这题的Code也可以没有重复数字的情况 ,也就是LeetCode Permutations问题。
AC Code
public class Solution { public List<List<Integer>> permuteUnique(int[] num) { List<List<Integer>> res = new ArrayList<List<Integer>>(); if(num == null || num.length == 0){ return res; } Arrays.sort(num); List<Integer> state = new ArrayList<Integer>(); dfs(res, state, num, new boolean[num.length]); return res; } void dfs(List<List<Integer>> res, List<Integer> state, int [] num, boolean [] used){ if(state.size() == num.length){ res.add(new ArrayList(state));//add a copy return; } for(int i = 0; i < num.length; i++){ if(i > 0 && !used[i-1] && num[i] == num[i-1]) continue;// judge duplicate number if(!used[i]){ state.add(num[i]); used[i] = true; dfs(res, state, num, used); state.remove(state.size() - 1); used[i] = false; } } } }
LeetCode Permutations II
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。