LeetCode | Intersection of Two Arrays

发表于   |   分类于   |     |   阅读次数

§349. Intersection of Two Arrays

Note:

  • Each element in the result must be unique. -> use set
  • The result can be in any order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
//java
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];
        Set<Integer> hs = new HashSet<Integer>();
        for (int i = 0; i < nums1.length; i++) {
            hs.add(nums1[i]); 
        }
        Set<Integer> res = new HashSet<Integer>();
        
        for(int i = 0;i < nums2.length;i++){
            if (hs.contains(nums2[i])) {
                res.add(nums2[i]);
                hs.remove(nums2[i]); 
            }
        }
        int[] res_ = new int[res.size()];
        int i = 0;
        for (Integer num : res) {
            res_[i++] = num; 
        }
        return res_; 
    }
/*
Using Stream in java 8
Set<Integer> set = Arrays.stream(nums2).boxed().collect(Collectors.toSet());
return Arrays.stream(nums1).distinct().filter(e-> set.contains(e)).toArray();
*/
1
2
3
4
5
6
7
8
9
//c++
	vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    	unordered_set<int> s(nums1.begin(), nums1.end());
	    vector<int> ans;
	    for (int num : nums2)
	        if (s.erase(num))
	            ans.push_back(num);
	    return ans;     
    }

§Follow up

  • If sorted?
    1. Use 2 pointers. O(M+N)
    2. Binary search. O(MlogN) or O(NlogM)

§350. Intersection of Two Arrays II

Note:

  • Each element in the result should appear as many times as it shows in both arrays.
  • The result can be in any order.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//java
public int[] intersect(int[] nums1, int[] nums2) {
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        ArrayList<Integer> res = new ArrayList<Integer>();
        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);
        }
        for (int i = 0; i < nums2.length; i++){
            if (map.containsKey(nums2[i]) && map.get(nums2[i]) > 0){
                res.add(nums2[i]);
                map.put(nums2[i],map.get(nums2[i])-1);
            }
        }
        int[] res_ = new int[res.size()];
        int i = 0;
        for (Integer num : res)
            res_[i++] = num;
        return res_;
    }
1
2
3
4
5
6
7
8
//java 8 using Strem
Map<Integer, Long> map = Arrays.stream(nums2).boxed().collect(Collectors.groupingBy(e->e, Collectors.counting()));
return Arrays.stream(nums1).filter(e ->{
        if(!map.containsKey(e)) return false;
        map.put(e, map.get(e) - 1);
        if(map.get(e) == 0) map.remove(e);
        return true;
    }).toArray();
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
//Another solution in C++
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int n1 = nums1.size(), n2 = nums2.size();
        int i = 0, j =0;
        vector<int> ans;
        while (i<n1 && j<n2){
        	if (nums1[i]==nums2[j]){
        		ans.push_back(nums1[i]);
        		i++,j++;
        	}
        	else if (nums1[i]>nums2[j])
        		j++;
        	else 
        		i++;
        }
        return ans;
    }

Follow up:

  • What if the given array is already sorted? How would you optimize your algorithm?

    Use 2 pointers, O(M+N)

  • What if nums1’s size is small compared to nums2’s size? Which algorithm is better?

    Use the smaller array to construct the counter hash.

  • 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?

    Divide and conquer.

    Do repeatedly: Slice nums2, caculate intersections, write partial results back to the memory.