友情支持
如果您觉得这个笔记对您有所帮助，看在D瓜哥码这么多字的辛苦上，请友情支持一下，D瓜哥感激不尽，😜
|
|
有些打赏的朋友希望可以加个好友，欢迎关注D 瓜哥的微信公众号，这样就可以通过公众号的回复直接给我发信息。
公众号的微信号是: jikerizhi。因为众所周知的原因，有时图片加载不出来。 如果图片加载不出来可以直接通过搜索微信号来查找我的公众号。 |
47. Permutations II
Given a collection of numbers that might contain duplicates, return all possible unique permutations.
Example:
Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]思路分析
-
一刷
-
二刷
-
三刷
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
33
34
35
36
37
38
39
40
41
42
/**
* Runtime: 1 ms, faster than 100.00% of Java online submissions for Permutations II.
* Memory Usage: 41.6 MB, less than 11.94% of Java online submissions for Permutations II.
*
* @author D瓜哥 · https://www.diguage.com
* @since 2020-01-27 20:29
*/
public List<List<Integer>> permuteUnique(int[] nums) {
if (Objects.isNull(nums) || nums.length == 0) {
return Collections.emptyList();
}
Arrays.sort(nums);
boolean[] used = new boolean[nums.length];
List<List<Integer>> result = new ArrayList<>();
backtrack(nums, 0, used, result, new ArrayDeque<>());
return result;
}
private void backtrack(int[] nums, int startIndex, boolean[] used,
List<List<Integer>> result, Deque<Integer> current) {
if (nums.length == startIndex) {
result.add(new ArrayList<>(current));
return;
}
for (int i = 0; i < nums.length; i++) {
if (!used[i]) {
// 修改 2：在 used[i - 1] 刚刚被撤销的时候剪枝，
// 说明接下来会被选择，搜索一定会重复，故"剪枝"
if (i > 0 && nums[i - 1] == nums[i] && !used[i - 1]) {
continue;
}
used[i] = true;
current.addLast(nums[i]);
backtrack(nums, startIndex + 1, used, result, current);
current.removeLast();
used[i] = false;
}
}
}
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
33
34
35
36
37
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-09 16:41:05
*/
public List<List<Integer>> permuteUnique(int[] nums) {
if (nums == null || nums.length == 0) {
return Collections.emptyList();
}
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
Arrays.sort(nums);
backtrack(nums, used, result, new ArrayList<>());
return result;
}
private void backtrack(int[] nums, boolean[] used,
List<List<Integer>> result, List<Integer> perm) {
if (perm.size() == nums.length) {
result.add(new ArrayList<>(perm));
return;
}
// 前面进行了排序，
// 如果不排序，也可以使用Set来记录同一层元素的使用情况，重复就跳过
int pre = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
if (used[i] || nums[i] == pre) {
continue;
}
used[i] = true;
pre = nums[i];
perm.add(nums[i]);
backtrack(nums, used, result, perm);
perm.remove(perm.size() - 1);
used[i] = false;
}
}
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
/**
* @author D瓜哥 · https://www.diguage.com
* @since 2024-07-09 16:41:05
*/
public List<List<Integer>> permuteUnique(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> result = new ArrayList<>();
boolean[] used = new boolean[nums.length];
backtrack(nums, result, used, new ArrayList<>(nums.length));
return result;
}
private void backtrack(int[] nums, List<List<Integer>> result,
boolean[] used, List<Integer> path) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
if (0 < i && nums[i - 1] == nums[i] && !used[i - 1]) {
continue;
}
used[i] = true;
path.addLast(nums[i]);
backtrack(nums, result, used, path);
path.removeLast();
used[i] = false;
}
}
思考：去重剪枝的判断是怎么实现的？