O(log(min(m,n))) C++ Solution


  • 0
    E

    O(log(min(m,n))) method in C++:

    class Solution {
    public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int p11=0,p12=nums1.size()-1,p21=0,p22=nums2.size()-1;
        int step;
        vector<int> finalBuffer(8);
        int finalBufferP=0;
        if(nums1.size()==0)
            return findMedian(nums2,0,nums2.size()-1);
        if(nums2.size()==0)
            return findMedian(nums1,0,nums1.size()-1);
        while((p12-p11)>1&&(p22-p21)>1)
        {
            if(findMedian(nums1,p11,p12)<findMedian(nums2,p21,p22))
            {
                step=p12-p11>p22-p21?(p22-p21)/2:(p12-p11)/2;
                p11+=step;
                p22-=step;
            }
            else
            {
                step=p12-p11>p22-p21?(p22-p21)/2:(p12-p11)/2;
                p21+=step;
                p12-=step;
            }
        }
    
        for(int i=1;i<3;i++)
        {
            if((p11+p12)/2-i>=p11) finalBuffer[finalBufferP++]=nums1[(p11+p12)/2-i];
            if((p11+p12+1)/2+i<=p12) finalBuffer[finalBufferP++]=nums1[(p11+p12+1)/2+i];
            if((p21+p22)/2-i>=p21) finalBuffer[finalBufferP++]=nums2[(p21+p22)/2-i];
            if((p21+p22+1)/2+i<=p22) finalBuffer[finalBufferP++]=nums2[(p21+p22+1)/2+i];
        }
    	finalBuffer[finalBufferP++] = nums1[(p11 + p12) / 2];
    	finalBuffer[finalBufferP++] = nums2[(p21 + p22) / 2];
    	if ((p11 + p12) / 2 != (p11 + p12 + 1) / 2)
    		finalBuffer[finalBufferP++] = nums1[(p11 + p12 + 1) / 2];
    	if ((p21 + p22) / 2 != (p21 + p22 + 1) / 2)
    		finalBuffer[finalBufferP++] = nums2[(p21 + p22 + 1) / 2];
    
        sort(finalBuffer.begin(),finalBuffer.begin()+finalBufferP);
        return findMedian(finalBuffer,0,finalBufferP-1);
        
        
    }
    
    double findMedian(vector<int>& nums,int p1,int p2)
    {
        return (double)(nums[(p1+p2)/2]+nums[(p1+p2+1)/2])/2.0;
    }
    };

  • 0
    R

    super untidy code


Log in to reply
 

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