Share my O(log(min(m,n)) solution


  • 10
    K

    A fact::

    if medianA is the median of array A, and medianB is the median of array B,

    then the median of the two array is between medianA and medianB.

    suppose medianA < medianB,

    when we remove some elements that are smaller than medianA in A

    and remove the same number of elements that are larger than meidanB in B,

    the problem become smaller but the median remains the same;

    suppose size(A) < size(B)

    usually half of the array of A are removed every time

    until there are less than 2 elements in A

    so it takes O( log(min(m,n))) before we stop the loop.

    By far, we got less than 2 elements left in A and still some elements in B.

    we can find the median of them easily in O(1)

    double findMedianSortedArrays(int A[], int m, int B[], int n) {
    
    	int lA = 0;
    	int lB = 0;
    	int rA = m - 1;
    	int rB = n - 1;
    
    	while (lA < rA && lB < rB){
    		
    		int sumA = lA + rA;
    		double medianA = (sumA & 0x0001)? 0.5 * (A[ sumA/2 ] + A[ sumA/2 + 1 ]) : A[ sumA/2];
    
    		int sumB = lB + rB;
    		double medianB = (sumB & 0x0001)? 0.5 * (B[ sumB/2 ] + B[ sumB/2 + 1 ]) : B[ sumB/2];
    
    		if (medianA == medianB)
    			return medianA;
    
    		// "step" is how many elements we can remove on this run
    		int step = std::min(rA - lA, rB - lB) / 2;  
    
    		if (step == 0)
    			break; // no numbers can be remvoed, means the size of (the shorter array) <= 2.
    
    		if (medianA < medianB){
    			lA += step;
    			rB -= step;
    		}else{
    			rA -= step;
    			lB += step;
    		}
    
    	}
    	// since half the shorter array are removed in each run,
    	// it takes only O(log(min(m,n))) to finish the loop
        
    
    	int sumB = lB + rB;
    	int sumA = lA + rA;
    
    	int * pn = A;
    	int * p1 = B;
    	int l = lB;
    	int r = rB;
    	int sum = sumA;
    	int count = rA - lA + 1;
    
    	if ((rA - lA) < (rB - lB)){
    		pn = B;
    		p1 = A;
    		l = lA;
    		r = rA;
    		sum = sumB;
    		count = rB - lB + 1;
    	}
    	
    	// now pn has more elements than p1 ,
        //and  p1 has less than 2 elements;
    
    	// the median can be determined by these elements:
    	// 1. elements around the middle of pn 
    	// 2. all element of p1 (0,1,2)
        // we put them into  	vector<int> vec;
    	vector<int> vec;
    
    	if (count % 2){      //------ [sum/2-1] [ sum/2 ] [ sum/2+1 ] --------
    		vec.push_back(pn[sum/2]);
    		if (count > 1){
    			vec.push_back(pn[sum/2 -1]);
    			vec.push_back(pn[sum/2 +1]);
    		}
    	}else{               //------ [sum/2-1] [ sum/2 ] [ sum/2+1 ] [sum/2+2] --------
    		vec.push_back(pn[sum/2]);
    		vec.push_back(pn[sum/2 + 1]);
    		if (count > 2){
    			vec.push_back(pn[sum/2 - 1]);
    			vec.push_back(pn[sum/2 + 2]);
    		}
    	}
    	
    
    	for (int i = l; i <= r; ++i) // r - l < = 1,  O(1)
    		vec.push_back(p1[i]);
    
    	// now vec contains the elements that are realy needed to get the median
    	// in ther words, the median of vec is equal to the median of the two original arrays.
    	sort(vec.begin(),vec.end());  //  vec.size() <= 6, O(1)
    
    	if (vec.size() % 2)
    		return vec[vec.size()/2];
    	else
    		return (vec[vec.size()/2 - 1] + vec[vec.size()/2]) * 0.5;
    	
    }

Log in to reply
 

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