All the Follow up Solution


  • 2
    Y

    1.What if the given array is already sorted? How would you optimize your algorithm?

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            vector<int> res;
            if(nums1.empty() || nums2.empty())
                return res;
            for(int i=0,j=0; i<nums1.size() && j<nums2.size(); ) {
                if(nums1[i] == nums2[j]) {
                    res.push_back(nums2[j]);
                    ++j;
                    ++i;
                }else if(nums1[i] < nums2[j]) {
                    ++i;
                }else if(nums1[i] > nums2[j]) {
                    ++j;
                }
            }
            return res;
        }
    };
    

    2.What if nums1's size is small compared to nums2's size? Which algorithm is better?

    class Solution {
    public:
        vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
            unordered_map<int, int> mymap;
            vector<int> res;
            for(auto it : nums1) {
                mymap[it]++;
            }
            for(auto it : nums2) {
                if(--mymap[it] >= 0) {
                    res.push_back(it);
                }
            }
            return res;
    
        }
    };

Log in to reply
 

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