Description
Given two arrays, write a function to compute their intersection.
Each element in the result should appear as many times as it shows in both arrays.The result can be in any order.
Example
Example1
Input:
nums1 = [1, 2, 2, 1], nums2 = [2, 2]
Output:
[2, 2]
Example2
Input:
nums1 = [1, 1, 2], nums2 = [1]
Output:
[1]
Challenge
- What if the given array is already sorted? How would you optimize your algorithm?
- What if nums1’s size is small compared to num2’s size? Which algorithm is better?
- What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?
Solution1 - 最少空间复杂度 O(n∩m)
时间复杂度 O(mlogm) + O(nlogn)，空间复杂度 O(n∩m) 。
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null)
return null;
if (nums1.length == 0 || nums2.length == 0)
return new int[0];
Arrays.sort(nums1);
Arrays.sort(nums2);
LinkedList<Integer> list = new LinkedList<>();
int i = 0, j = 0;
while (i < nums1.length && j < nums2.length) {
if (nums1[i] == nums2[j]) {
list.add(nums1[i]);
i++;
j++;
} else if (nums1[i] > nums2[j])
j++;
else if (nums1[i] < nums2[j])
i++;
}
int[] res = new int[list.size()];
i = 0;
for (int e : list) {
res[i] = e;
i++;
}
return res;
}
Solution2 - 使用 Hashmap
时间复杂度 O(m) + O(n)，空间复杂度 O(m) + O(n∩m) 。
public int[] intersection(int[] nums1, int[] nums2) {
if (nums1 == null || nums2 == null)
return null;
if (nums1.length == 0 || nums2.length == 0)
return new int[0];
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
if (map.containsKey(nums1[i])) {
map.put(nums1[i], map.get(nums1[i]) + 1);
} else {
map.put(nums1[i], 1);
}
}
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < nums2.length; i++) {
if (map.containsKey(nums2[i]) && map.get(nums2[i]) != 0) {
list.add(nums2[i]);
map.put(nums2[i], map.get(nums2[i]) - 1);
}
}
int[] res = new int[list.size()];
int i = 0;
for (int e : list) {
res[i] = e;
i++;
}
return res;
}