[LeetCode] 349. Intersection of Two Arrays

[frdmu]

Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.

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]
Explanation: [4,9] is also accepted.

Constraints:

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

解法一：
求两个数组的交集，思路很简单，用hashtable，涉及到去重，所以这里的hashtable用Set表示。代码如下：

class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> s(nums1.begin(), nums1.end()), res;

        for (auto e : nums2) {
            if (s.count(e)) res.insert(e);
        }
        
        return vector<int>(res.begin(), res.end());
    }
};

解法二：
将其中一个数组排序，遍历另一个数组，如果另一个数组的元素在已排序的数组中，则该元素为两个数组的交集。用二分查找进行搜索。代码如下：

class Solution {
public:
    bool find(vector<int> nums, int target) {
        int left = 0, right = nums.size();
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return true;
            else if (nums[mid] > target) right = mid;
            else left = mid + 1;
        }
        return false;
    } 
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        unordered_set<int> res;

        sort(nums1.begin(), nums1.end());
        for (auto e : nums2) {
            if (find(nums1, e)) 
                res.insert(e);
        }
        
        return vector<int>(res.begin(), res.end());
    }
};