C++ two pointer easy understand solution


  • 5
    S
    class Solution {
    public:
        vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
            sort(nums1.begin(), nums1.end());
            sort(nums2.begin(), nums2.end());
            int n1 = (int)nums1.size(), n2 = (int)nums2.size();
            int i1 = 0, i2 = 0;
            vector<int> res;
            while(i1 < n1 && i2 < n2){
                if(nums1[i1] == nums2[i2]) {
                    res.push_back(nums1[i1]);
                    i1++;
                    i2++;
                }
                else if(nums1[i1] > nums2[i2]){
                    i2++;
                }
                else{
                    i1++;
                }
                while(i1 > 0 && i1 < n1 && nums1[i1] == nums1[i1 - 1]) i1++;
                while(i2 > 0 && i2 < n2 && nums2[i2] == nums2[i2 - 1]) i2++;
            }
            return res;
        }
    };

  • 1
    X

    yours is the best, if output required to be ordered.


  • 0
    S

    Simple and easy to understand.

    One suggestion though,

    i1 < n1 is not required in
    while(i1 > 0 && i1 < n1 && nums1[i1] == nums1[i1 - 1]) as we are already checking this in the first while loop.

    Same for i2< n2 in
    while(i1 > 0 && i1 < n1 && nums1[i1] == nums1[i1 - 1])


  • 0
    W

    The running time would be nlogn?


  • 0
    G

    @saurabh3 the check is needed, otherwise i1 may go out of boundary by i1++.


Log in to reply
 

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