Problem
Given two arrays, write a function to compute their intersection.
Example 1:
Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2,2]
Example 2:
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [4,9]
Note:
Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.
Follow up:
What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2'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?
Solution
One solution is to sort the arrays, then use 2 pointers to find the solution. The time cost is O(NlogN + MlogM), the space cost is O(1).
import java.util.*;
public class InterSection {
public static List<Integer> findInterSection(int[] a, int[] b) {
//[4 5 9], nums2 = [4 4 8 9 9]
Arrays.sort(a);
Arrays.sort(b);
List<Integer> result = new ArrayList<>();
int N = a.length; //3
int M = b.length; //5
int i = 0, j = 0;
while(i < N && j < M) {
if(a[i] < b[j]) i++; //2
else if(a[i] > b[j]) j++; //3
else {
result.add(a[i]); //4 9
i++; //3
j++; //4
}
}
return result;
}
public static void main(String...args) {
int[] a = new int[]{1,2,2,1};
int[] b = new int[]{2,2};
for(int i : findInterSection(a, b)) {
System.out.print(" " + i);
}
}
}
public class InterSection {
public static List<Integer> findInterSection(int[] a, int[] b) {
//[4 5 9], nums2 = [4 4 8 9 9]
Arrays.sort(a);
Arrays.sort(b);
List<Integer> result = new ArrayList<>();
int N = a.length; //3
int M = b.length; //5
int i = 0, j = 0;
while(i < N && j < M) {
if(a[i] < b[j]) i++; //2
else if(a[i] > b[j]) j++; //3
else {
result.add(a[i]); //4 9
i++; //3
j++; //4
}
}
return result;
}
public static void main(String...args) {
int[] a = new int[]{1,2,2,1};
int[] b = new int[]{2,2};
for(int i : findInterSection(a, b)) {
System.out.print(" " + i);
}
}
}
Another solution is to use a hash map to store the character count in array 1, then go through the array 2, add the elements that exist in the hash map and decrease the count. When the count decrease to 0, we need to remove the element.
The time cost will be O(M + N), the space cost is O(M)
