leetcode解题: Intersection of Two Arrays II (350)

发表于 | 分类于

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

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?

解法1：HashTable O(N) Space + O(N + M) Time

将其中一个构建hashtable，记录每个数字出现的次数。扫描第二个数组，每当找到一样的次数大于0的数字则加入res，加入结束以后需要将hashtable中出现次数-1
C++

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) {
        vector<int> res;
        unordered_map<int, int> map;
        for (int num: nums1) {
            ++map[num];
        }
        for (int num : nums2) {
            if (map[num] > 0) {
                res.emplace_back(num);
                --map[num];
            }
        }
        return res;
    }
};

Java

1

Follow up：

如果是已经排序了的数组，那么不需要用hashtable，可以用two pointers解决。简化到了O(N + M) TIME + O(1) Space
对于follow up的回答：这个blog给了挺好的答案。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
pubic：
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
      vector<int> res;
      int ptr1 =0, ptr2 = 0;
      while (ptr1 < nums1.size() && ptr2 < nums2.size()) {
        if (nums1[ptr1] < nums2[ptr2]) {
          ++ptr1;
        } else if (nums1[ptr1] > nums2[ptr2]) {
          ++ptr2;
      } else {
        res.emplace_back(nums1[ptr1]);
        ++ptr1;
        ++ptr2;
      }
    }
    return res;
}