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.
Answer1 : Works but is a bad answer O(n^2)
Use a hashmap to store the indexs of nums1 and nums2 matched.
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer,Integer> hm = new HashMap<Integer, Integer>();
ArrayList<Integer> arrList = new ArrayList<Integer>();
for(int i=0; i<nums1.length; i++){
for(int j=0; j<nums2.length; j++){
if(nums1[i]==nums2[j]){
if(!hm.containsKey(i) && !hm.containsValue(j)){
hm.put(i, j);
arrList.add(nums1[i]);
}
}
}
}
int[] result = new int[arrList.size()];
for(int i=0; i<arrList.size(); i++){
result[i] = arrList.get(i);
}
return result;
}
}
Better Solution O(n):
class Solution {
public int[] intersect(int[] nums1, int[] nums2) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i: nums1){
if(map.containsKey(i)){
map.put(i, map.get(i)+1);
}else{
map.put(i, 1);
}
}
ArrayList<Integer> list = new ArrayList<Integer>();
for(int i: nums2){
if(map.containsKey(i)){
if(map.get(i)>1){
map.put(i, map.get(i)-1);
}else{
map.remove(i);
}
list.add(i);
}
}
int[] result = new int[list.size()];
int i =0;
while(i<list.size()){
result[i]=list.get(i);
i++;
}
return result;
}
}
