47、全排列 II
题目：
题解：
此题在46、全排列的基础上，使数组有重复项，并要求排列结果不能重复。分析便知此题是在46、全排列的DFS递归回溯的基础上再加上一个典型的排序去重。
去重的方式就是对数组排序后，在递归中的每一层循环迭代都判断nums[i]是否与nums[i-1]相等（前提是i不是当前层循环的第一位）并且used[i-1]是否为false，如果相等，且used[i-1]为false（如果为true说明已经加入tmp_list，那么nums[i-1]属于上一层的元素了，只有同层元素相邻相等才会产生重复），则直接continue即可，因为必然与nums[i-1]迭代得出的排列结果相同（因为同层且剩下的元素相等）。
DFS递归回溯，排序后，同层相邻相同且未加入到tmp_list中则continue去重。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
int length = nums.length;
List<List<Integer>> res = new ArrayList<>();
if (length == 0) {
return res;
}
List<Integer> tmp_list = new ArrayList<>();
boolean[] used = new boolean[length];
Arrays.sort(nums);
bfs(0, nums, used, tmp_list, res, length);
return res;
}
public void dfs(int depth, int[] nums, boolean[] used, List<Integer> list, List<List<Integer>> res, int length) {
if (depth == length) {
res.add(new ArrayList<Integer>(list));
return;
}
for (int i = 0; i < length; i++) {
if(i != 0 && nums[i] == nums[i-1] && !used[i-1]) {
continue;
}
if(used[i] == false) {
used[i] = true;
list.add(nums[i]);
bfs(depth + 1, nums, used, list, res, length);
list.remove(list.size() - 1);
used[i] = false;
}
}
}
}
|
上一篇：10、iptables——Filter表
下一篇：46-全排列
