四刷 06/2022
Version #1 DFS with HashSet
写了一个错误的swap的版本
通过i != index && nums[i] == nums[i - 1] {continue} 来去重，但是问题是array一开始是有序的，但是在过程中已经swap过了所以不再有序了，所以只能用hashset来去重
另外三刷的答案里面一边iterate map一边更新有concurrent modification的issue，所以也不好
自己又写了一个带hashset version的
看答案里面还有一个做法就是检查nums[i]==nums[i - 1]的时候必须num[i-1] is used，这个方法也不错，可以下次写一写
Time O(N*N!)
Space O(N)
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
boolean[] used = new boolean[nums.length];
List<List<Integer>> result = new ArrayList<>();
permuteHelper(nums, new ArrayList<>(), used, result);
return result;
}
private void permuteHelper(int[] nums, List<Integer> path, boolean[] used, List<List<Integer>> result) {
if (path.size() == nums.length) {
result.add(new ArrayList<>(path));
return;
}
Set<Integer> seen = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
if (used[i]) {
continue;
}
// This number is the first time seen in this layer
if (seen.add(nums[i])) {
used[i] = true;
path.add(nums[i]);
permuteHelper(nums, path, used, result);
used[i] = false;
path.remove(path.size() - 1);
}
}
}
}
三刷
Version #1 DFS
没有用swap的方法
用hashmap来处理重复的问题
Time O(N * N!)
Space O(N)
Runtime: 3 ms, faster than 86.82% of Java online submissions for Permutations II.
Memory Usage: 43.1 MB, less than 85.89% of Java online submissions for Permutations II.
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
Map<Integer, Integer> count = new HashMap<>();
for (int num : nums) {
count.put(num, count.getOrDefault(num, 0) + 1);
}
dfs(nums.length, count, new ArrayList<>(), result);
return result;
}
private void dfs(int N, Map<Integer, Integer> count, List<Integer> path, List<List<Integer>> result) {
if (path.size() == N) {
result.add(new ArrayList<>(path));
return;
}
for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
int num = entry.getKey();
int cnt = entry.getValue();
if (cnt == 0) {
continue;
}
count.put(num, cnt - 1);
path.add(num);
dfs(N, count, path, result);
count.put(num, cnt);
path.remove(path.size() - 1);
}
}
}
跟上次的思路一样
一上来就做错了，因为没有考虑如果当前的index和后面的swap，如果后面有某两个值是一样的，这两次产生的swap结果就是一样的
所以必须去重
这里用了一个hashset来避免和当前index swap的值有重复
我觉得如果考虑garbage collection的话 space 是O(n)
不考虑的话 是O(n!)
Ref
Since we only need permutations of the array, the actual "content" does not change, we could find each permutation by swapping the elements in the array.
The idea is for each recursion level, swap the current element at 1st index with each element that comes after it (including itself). For example, permute[1,2,3]:
At recursion level 0, current element at 1st index is 1, there are 3 possibilities: [1] + permute[2,3], [2] + permute[1,3], [3] + permute[2,1].
Take "2+permute[1,3]" as the example at recursion level 0. At recursion level 1, current elemenet at 1st index is 1, there are 2 possibilities: [2,1] + permute[3], [2,3] + permute[1].
... and so on.
Let's look at another example, permute[1,2,3,4,1].
At recursion level 0, we have [1] + permute[2,3,4,1], [2] + permute[1,3,4,1], [3] + permute[2,1,4,1], [4] + permute[2,3,1,1], [1] + permute[2,3,4,1].
1 has already been at the 1st index of current recursion level, so the last possibility is redundant. We can use a hash set to mark which elements have been at the 1st index of current recursion level, so that if we meet the element again, we can just skip it.
Time O(n!)
13.77 %
class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
if (nums == null || nums.length == 0) {
return result;
}
dfs(nums, 0, result);
return result;
}
// Try to swap index with any index larger than or equal to itself
// Swapping with itself means not swap
// Remember back tracking
// if (index == nums.length - 1) can't swap any more, add to result
private void dfs(int[] nums, int index, List<List<Integer>> result) {
if (index == nums.length) {
result.add(Arrays.stream(nums).boxed().collect(Collectors.toList()));
return;
}
Set<Integer> visited = new HashSet<>();
for (int i = index; i < nums.length; i++) {
if (visited.add(nums[i])) {
swap(nums, index, i);
dfs(nums, index + 1, result);
swap(nums, index, i);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
一刷
必须要说这个题看上去和Permutations I差不多
按照 一般的套路 就是加入一个if (i == start || nums[i] != nums[i - 1])来去除重复的选择
但是！！这是不对的
因为在I里面为了快速，用的是swap的方法
在这种情况下，原数组里面nums[i] != nums[i - 1]就不再成立了
所以这种方法是不能用的
(有人说变成(i == start || nums[i] != nums[start])然后用HashSet来保存结果的list防止重复，这个方法存疑。而且感觉HashSet存List<Integer>复杂度太高了，因为每次都要遍历整个list求它的hashcode)
所以回归最淳朴的方法，用一个boolean array记录每个数是否被遍历过
75.70%
public class Solution {
public List<List<Integer>> permuteUnique(int[] nums) {
List<List<Integer>> result = new ArrayList<List<Integer>>();
if (nums == null || nums.length == 0) return result;
Arrays.sort(nums);
boolean[] visited = new boolean[nums.length];
helper(nums, result, new ArrayList<Integer>(), visited);
return result;
}
private void helper(int[] nums, List<List<Integer>> result, List<Integer> path, boolean[] visited) {
//Base case
if (path.size() == nums.length) {
result.add(new ArrayList<Integer>(path));
return;
}
for (int i = 0; i < nums.length; i++) {
//Check Duplicates or visited
if (visited[i] || (i != 0 && nums[i] == nums[i - 1] && !visited[i - 1])) continue;
path.add(nums[i]);
visited[i] = true;
helper(nums, result, path, visited);
//backtracking
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
No comments:
Post a Comment