349. Intersection of Two Arrays

找兩個陣列的交集, 注意一些細節, 例如哪個陣列比較大, 是否有空陣列等等

首先我們使用到hashtable

可以將時間複雜度壓在O(m+n)

class Solution {
  public:
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        std::unordered_map<int, int> table;
        if (nums1.size() < nums2.size()) {
            return intersection(nums2, nums1);
        }
        if (nums1.size() == 0 || nums2.size() == 0) {
            return std::vector<int>{};
        }
        for (auto &n : nums1) {
            if (table.count(n) == 0) {
                table[n] = 1;
            }
        }
        vector<int> res;
        for (int i = 0; i < nums2.size(); i++) {
            if (table.count(nums2[i])) {
                if (table[nums2[i]] > 0) {
                    res.push_back(nums2[i]);
                    table[nums2[i]] = 0;
                }
            }
        }
        return res;
    }
};

但這題是我在binary_search上看到的高頻題, 應該是可以將時間複雜度壓到log層級,

只是看到的當下沒有想到就是了, 怎麼做呢？

先把一個較大的陣列進行排序

接著將較小陣列每個值對大陣列做binary search, 找得到就加到set, 避免處理重複

class Solution {
  public:
    static inline bool BinarySearch(vector<int> &array, int target) {
        int l = 0;
        int r = array.size() - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (array[mid] == target) {
                return true;
            } else if (target < array[mid]) {
                r = mid - 1;
            } else {
                l = mid + 1;
            }
        }
        return false;
    }
    vector<int> intersection(vector<int> &nums1, vector<int> &nums2) {
        if (nums1.size() < nums2.size()) {
            return intersection(nums2, nums1);
        }
        if (nums2.size() == 0) {
            return std::vector<int>{};
        }
        sort(nums1.begin(), nums1.end());
        std::unordered_set<int> res;
        for (auto &n : nums2) {
            if (BinarySearch(nums1, n)) {
                res.insert(n);
            }
        }
        return std::vector<int>(res.begin(), res.end());
    }
};