My code:
public class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null) {
return null;
}
HashSet<Integer> set = new HashSet<Integer>();
HashSet<Integer> ret = new HashSet<Integer>();
for (int i = 0; i < nums1.length; i++) {
set.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
if (set.contains(nums2[i]) && !ret.contains(nums2[i])) {
ret.add(nums2[i]);
}
}
int[] arr = new int[ret.size()];
int counter = 0;
for (Integer curr : ret) {
arr[counter++] = curr;
}
return arr;
}
}
比较简单。然后看了答案，发现一共有三种做法。
https://discuss.leetcode.com/topic/45685/three-java-solutions/2
第一种就是我这种
time complexity: O(n)
space complexity: O(n)
第二种是，给两个数组都排序，然后类似于 merge sort,找 Intersection
time complexity: O(n logn)
space complexity: O(n)
第三种是，给一个数组排序，然后另外一个数组的元素，都去这个数组里面做 Binary search,如果能找到，就是 Intersection
time complexity: O(n logn)
space complexity: O(n)
