Intersection of Two Arrays

• Lintcode : 547
• Level : Easy

Problem

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

Example
Example 1:

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

Input: nums1 = [1, 2], nums2 = [2], 
Output: [2].
Challenge
Can you implement it in three different algorithms?

Notice
Each element in the result must be unique.
The order of the results needs to be ascending

Concept & Algorithm

筆記

Time Complexity & Space Complexity

sol 1:

time : O(n)
space: O(n)

sol 2:

time : O(n)
space: O(1)

Answer

// sol 1:
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        set<int> map(nums1.begin(), nums1.end());
        vector<int> ans;
        for (auto i : nums2) {
            if(map.find(i) != map.end()) {
                ans.push_back(i);
                map.erase(i);
            }
        }
        return ans;
    }
};

// sol 2:
class Solution {
public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        if (nums1.size() == 0 || nums2.size() == 0) return {};
        sort(nums1.begin(), nums1.end());
        sort(nums2.begin(), nums2.end());
        vector<int> ans;
        for (int i = 0; i < nums1.size(); i++) {
            if (i > 0 && nums1[i] == nums1[i - 1]) continue;
            if (binarySearch(nums2, nums1[i])) {
                ans.push_back(nums1[i]);
            }
        }
        return ans;
    }
    bool binarySearch(vector<int> &nums2, int target) {
        int l = 0, r = nums2.size() - 1;
        while (l + 1 < r) {
            int mid = l + (r - l) / 2;
            if (nums2[mid] == target) return true;
            else if (nums2[mid] < target) {
                l = mid;
            }
            else r = mid;
        }
        if (nums2[l] == target) return true;
        if (nums2[r] == target) return true;
        return false;
    }
};

tags: Binary Search

​