8ms C++ solution using sorting


  • 0
    A
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
    
            if (nums1.empty() || nums2.empty()) {
                return vector<int>();
            }
    
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            
            return nums2[0] < nums1[0] ? intersection2(nums1, nums2) : intersection2(nums2, nums1);
        }
        vector<int> intersection2(vector<int>& nums1, vector<int>& nums2) {
            
            vector<int> res;
            
            size_t pos1 = 0;
            size_t pos2 = 0;
            
            size_t size1 = nums1.size();
            size_t size2 = nums2.size();
            while (true) {
                while (pos2 < size2 && nums2[pos2] < nums1[pos1]) {
                    ++pos2;
                }
                if (pos2 == size2) {
                    break;
                }
                if (nums2[pos2] == nums1[pos1]) {
                    res.push_back(nums2[pos2++]);
                    while (pos2 < size2 && nums2[pos2]==nums2[pos2-1]) {
                        // Move forward if we have duplicates
                        ++pos2;
                    }
                }
                ++pos1;
                while (pos1 < size1 && nums1[pos1]==nums1[pos1-1]) {
                    // Move forward if we have duplicates
                    ++pos1;
                }
                    
                if (pos1 == size1) {
                    break;
                }
            }
            return res;
        }
    };
    

    For Intersection of Two Arrays II, we just need to remove the two while loops where we move forward in the case of duplicates


Log in to reply
 

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