[Fight] Summary of C++ implementations


  • 0

    Firstly, let us check the C++ implementation of the original problem ...

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            /** we can minimize the space cost by choose the smaller array to construct dictionary **/
            if (nums1.size() > nums2.size()) {
                return intersect(nums2, nums1);
            }
            unordered_map<int, int> lookup;
            for (const auto& num : nums1) {
                ++ lookup[num];
            }
            vector<int> result;
            for (const auto& num : nums2) {
                if (lookup[num] > 0) {
                    result.emplace_back(num);
                    --lookup[num];
                }
            }
            return result;
        }
    };
    

    So, how to optimize it if the 2 arrays are all in sorted order ...

    time: min(m, n) * log(max(m, n))
    space : O(1)

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            if (nums1.size() > nums2.size()) {
                return intersect(nums2, nums1);
            }
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            vector<int> result;
            auto it = nums2.cbegin();
            for (const auto& num : nums1) {
                it = lower_bound(it, nums2.cend(), num);
                if (it != nums2.end() && *it == num) {
                    result.emplace_back(*it++);
                }
            }
            return result;
        }
    };
    

    Next, let check a O(M+N) implementation if we are limited in memory.

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            if (nums1.size() > nums2.size()) {
                return intersect(nums2, nums1);
            }
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            vector<int> result;
            auto it1 = nums1.cbegin(), it2 = nums2.cbegin();
            while (it1 != nums1.cend() && it2 != nums2.cend()) {
                if (*it1 < *it2) {
                    ++it1;
                } else if (*it1 > *it2) {
                    ++it2;
                } else {
                    result.emplace_back(*it1);
                    ++it1, ++it2;
                }
            }
            return result;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.