1.题目描述

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

2.解法分析

我本来直接想用二分法求出结果，然后有了下面这个结果，结果发现当m+n为偶数时计算出来的结果不对，因为我最初的算法就是求中位数，而不是题目要求的两个中位数的平均值。

class Solution {

public:

vector
           
             twoSum(vector
            
              &numbers, int target) {
            
           

// Start typing your C/C++ solution below

// DO NOT write int main() function

unordered_set
           
             myHash;
           

vector
           
            ::iterator iter;
           

vector
           
             result;
           

result.assign(2,0);

if(target%2==0)

{

int count=0;

for(int i=0;i

{

if(numbers[i]==target/2)

{

if(count==0){result[0]=i+1;count++;

}

else

{

result[1]=i+1;return result;

}

}

}

}

for(iter=numbers.begin();iter!=numbers.end();++iter)

{

myHash.insert(*iter);        }

for(int i=0;i

{

myHash.erase(numbers[i]);

if(myHash.count(target-numbers[i])==1)

{

result[0]=i+1;break;

}

myHash.insert(numbers[i]);

}

for(int i=result[0];i

{

if((numbers[result[0]-1]+numbers[i])==target)

{

result[1]=i+1;break;

}

}

return result;

}

};

 

本来想修修补补，看看能不能够AC，结果弄了好半天烦死了，因此觉得应该会有比较统一的方法。结果搜寻到了一个很统一的方法，这个方法将找两个数组的中位数推广到了找两个数组中第k大的数字，有了这个思路代码就很简单了。

class Solution {

//more detail refer to: http://fisherlei.blogspot.com/2012/12/leetcode-median-of-two-sorted-arrays.html

//using the method of getting the kth number in the two sorted array to solve the median problem

//divide-and-conquer

//very clean and concise

public:

double findMedianSortedArrays(int A[], int m, int B[], int n) {

if((n+m)%2 ==0)

{

return (GetMedian(A,m,B,n, (m+n)/2) + GetMedian(A,m,B,n, (m+n)/2+1))/2.0;

}

else

return GetMedian(A,m,B,n, (m+n)/2+1);

}

int GetMedian(int a[], int n, int b[], int m, int k)//get the kth number in the two sorted array

{

//assert(a && b);

if (n <= 0) return b[k-1];

if (m <= 0) return a[k-1];

if (k <= 1) return min(a[0], b[0]);

//a: section1 section2

//b: section3 section4

if (b[m/2] >= a[n/2])

{

if ((n/2 + 1 + m/2) >= k)

return GetMedian(a, n, b, m/2, k);//abort section 4

else

return GetMedian(a + n/2 + 1, n - (n/2 + 1), b, m, k - (n/2 + 1)); //abort section 1

}

else

{

if ((m/2 + 1 + n/2) >= k)

return GetMedian( a, n/2,b, m, k);//abort section 2

else

return GetMedian( a, n, b + m/2 + 1, m - (m/2 + 1),k - (m/2 + 1));//abort section 3

}

}

};