Share my C++ solution, easy to understand.


  • 0
    B

    The general idea is simple.
    Use two pointers for each array to find out the middle two elements of all.
    Pad INT_MAX at end of each array will make the algorithm clearer.

    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) 
        {
            int n1 = nums1.size();
            int n2 = nums2.size();
            if(n1 + n2 == 0) return 0;
            
            nums1.insert(nums1.end(), INT_MAX); //Pad in case OOB.
            nums2.insert(nums2.end(), INT_MAX);
            
            int p1 = 0, p2 = 0; //Point to each array.
            int oldOne, newOne;
            for(int i = 0; i <= (n1 + n2) / 2; ++i) 
            {
                oldOne = newOne;
                if(nums1[p1] > nums2[p2]) newOne = nums2[p2++];
                else newOne = nums1[p1++];
            }
            
            if((n1 + n2) % 2 == 1) return newOne;               //Odd
            else return ((double)oldOne + (double)newOne) / 2;  //Even
    

  • 0
    H

    O(m+n), inappropriate solution.


Log in to reply
 

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