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

• 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;

}``````

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