349.Intersection of Two Arrays

Tags: Easy Binary Search

Links: https://leetcode.com/problems/intersection-of-two-arrays/

---

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

Example 1:

Input: nums1 = [1,2,2,1], nums2 = [2,2]
Output: [2]

Example 2:

Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
Output: [9,4]

Note:

• Each element in the result must be unique.
• The result can be in any order.

---

class Solution {
    int binarySearch(vector<int> & nums, int target) {
        int n = nums.size();
        if (n == 0) return -1;

        int left = 0, right = n -1;
        while (left <= right) {
            int middle  = left + ((right - left) >> 1);
            if (nums[middle] == target) return middle;
            else if (nums[middle] < target) left = middle + 1;
            else right = middle - 1;
        }

        return -1;
    }

public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        int n1 = nums1.size(), n2 = nums2.size();
        unordered_set<int> tmpStore;


        if (n1 < n2){
            sort(nums2.begin(), nums2.end());
            for (auto e : nums1){
                int pos = binarySearch(nums2, e);
                if (pos >= 0) tmpStore.insert(e);
            }
        } 
        else {
            sort(nums1.begin(), nums1.end());
            for (auto e : nums2){
                int pos = binarySearch(nums1, e);
                if (pos >= 0) tmpStore.insert(e);
            }
        }
        vector<int> result(tmpStore.begin(), tmpStore.end());

        return result;
    }
};

二分查找优化，思路是将一个数组排序，然后遍历另一个数组，把遍历到的每个数字在排序号的数组中用二分查找法搜索，如果能找到则放入结果set中，这里我们用到了set的去重复的特性，最后我们将set转为vector即可。

方法二，应用标准库算法set_intersection()：

class Solution { 
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        set<int> s1(nums1.begin(), nums1.end()), s2(nums2.begin(), nums2.end()), tmp;
        set_intersection(s1.begin(), s1.end(), s2.begin(), s2.end(), inserter(tmp, tmp.begin()));
        vector<int> result(tmp.begin(), tmp.end());

        return result;
    }
};

但是这种做法显然会慢于上一种，因为初始化s1, s2上花费了时间。总体上是$O(n)$。