Mind palace

some thoughts

0%

350. Intersection of Two Arrays II

Posted on Edited on In Disqus:
Symbols count in article: 3.4k Reading time ≈ 3 mins.

O(m + n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> m;
        for (int n : nums1) {
            ++m[n];
        }
        vector<int> res;
        for (int n : nums2) {
            if (m[n] > 0) {
                --m[n];
                res.push_back(n);
            }
        }
        return res;
    }
};

follow up #1
双指针 O(m + n) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        vector<int> res;
        //sort(begin(nums1), end(nums1));
        //sort(begin(nums2), end(nums2));
        int m = nums1.size(), n = nums2.size();
        for (int i = 0, j = 0; i < m && j < n;) {
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                ++i;
                ++j;
            } else if (nums1[i] < nums2[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return res;
    }
};

用iterator会清楚很多也好写
worst case O(mlogm + nlogn) time

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(begin(nums1), end(nums1));
        sort(begin(nums2), end(nums2));
        vector<int> res;
        for (int i = 0, j = 0, m = size(nums1), n = size(nums2); i < m && j < n;) {
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                ++i, ++j;
            } else if (nums1[i] < nums2[j]) {
                i = lower_bound(begin(nums1) + i + 1, end(nums1), nums2[j]) - begin(nums1);
            } else {
                j = lower_bound(begin(nums2) + j + 1, end(nums2), nums1[i]) - begin(nums2);
            }
        }
        return res;
    }
};

follow up #2
O(min(m,n)log(max(m,n)))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int m = nums1.size(), n = nums2.size();
        auto &&s = m < n ? nums1 : nums2;
        auto &&l = m < n ? nums2 : nums1;
        vector<int> res;
        auto it = l.begin();
        for (int x : s) {
            it = lower_bound(it, l.end(), x);
            if (it == l.end()) {
                break;
            } else if (*it == x) {
                res.push_back(x);
                ++it;
            }
        }
        return res;
    }
};

if m << n, O(min(m,n)log(max(m,n))) is close to O(logn) while O(m+n) is close to O(n)

follow up #3

  • If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
  • If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections. (similar to merge)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        int m = nums1.size(), n = nums2.size();
        vector<int> res;
        for (int i = 0, j = 0; i < m && j < n;) {
            if (nums1[i] == nums2[j]) {
                res.push_back(nums1[i]);
                ++i;
                ++j;
            } else if (nums1[i] < nums2[j]) {
                ++i;
            } else {
                ++j;
            }
        }
        return res;
    }
};
  • another approach is to build index for sorted nums2, if nums2 is [1,2,3,4,5,6,7,8,9,10], we can build index [1:address, 3:address, 5:address, 7:address, 9:address], and put the indices in memory, each time we search the indices first and locate the chunk address in disk, then load the chunk in memory and do another round binary search of the chunk. the size of chunk must fit in the memory (indices are built based on this). because there might be some dup numbers, we can maintain a hashmap (or bloomfilter) in memory to tell how many dup numbers has already been searched (i.e., nums2 has only 4 number 5s but nums1 has 6 number 5s then the last 2 searches for number 5 will be aborted).