两个排序的数组A和B分别含有m和n个数，找到两个排序数组的中位数，要求时间复杂度应为O(log (m+n))。
您在真实的面试中是否遇到过这个题？ Yes 样例给出数组A = [1,2,3,4,5,6] B = [2,3,4,5]，中位数3.5
给出数组A = [1,2,3] B = [4,5]，中位数 3
挑战 标签 相关题目 分析：这道题折腾了好几天，今天总算弄明白了。可能我太笨了，如果在考试中遇到这种难度的题解个几天都解不出来@。@看到这个题的第一反应是把两个数组遍历一遍并组合到一个数组中，取中位数就很简单了。这样做的时间复杂度为O（m+n），可还是能通过测试，可能lintcode没有检测时间复杂度？
时间复杂度为O(m+n)的方法是在别人的方法之上，修修补补才能放在这个题目下运行起来的。。。心疼自己的智商
本题从时间复杂度来看就是采用二分法，该方法的核心是将原问题转变成一个寻找第k小数的问题（假设两个原序列升序排列），这样中位数实际上是第(m+n)/2小的数。所以只要解决了第k小数的问题，原问题也得以解决。因为A和B都是升序的，理想情况下假设A和B的个数都大于k/2(这里的k就是两个数组合起来的中位数(m+n)/2)。首先比较A[k/2-1]和B[k/2-1]
情况一：A[k/2-1]<B[k/2-1],则A[0]-A[k/2-1]的值必定在合并后的前k个元素中，换言之合并后的中位数第k个元素不可能出现在A[0]-A[k/2-1]这个区间。因为如果中位数出现在A[0]-A[k/2-1]这个区间，而且A[k/2-1]<B[k/2-1]表示这个中位数之后(k=（m+n）/2)有超过n-k/2+m-k/2即(m+n)/2个元素，这显然不符合中位数的定义，所以可以将A[0]-A[k/2-1]范围的元素抛弃，并将要寻找的中位数减去抛弃元素的个数。
二:当A[k/2-1]<B[k/2-1]时同上，抛弃B的部分元素。
三:当A[k/2-1]=B[k/2-1]时，说明已经找到了中位数，返回其中任意一个即可。
对于一些边界情况，当A或者B为空时，直接返回不为空的数组中位数;
当k=1时(因为每次递归都会改变中位数的值)，返回A和B中第一个元素较小者
因为这道题给的是向量vector的形式而不是数组，所以为了表示下标可能代码有点凌乱，下为代码
class Solution { public: /** * @param A: An integer array. * @param B: An integer array. * @return: a double whose format is *.5 or *.0 */ double findMedianSortedArrays(vector<int> A, vector<int> B) { int m=A.size(),n=B.size(); int s=m+n; if(s&0x01)//真为奇数 return findKth(A,B,0,0,m,n,s/2+1); else { double a=findKth(A,B,0,0,m,n,s/2); double b=findKth(A,B,0,0,m,n,s/2+1); return (a+b)/2; } // return (findKth(A,B,0,0,m,n,s/2)+findKth(A,B,0,0,m,n,s/2+1))/2; } private: double findKth(vector<int> A, vector<int> B,int start1,int start2,int m,int n,int k)//start1，start2代表每个vector起始的下标;m,n代表各vector剩余的元素个数 { //保证A是较短的数组,因为会出现数组长度小于k/2的情况，所以根据较小数组来定另一个数组 if(m>n)//m代表A的长度，n代表B的长度 return findKth(B,A,start2,start1,n,m,k); if(m==0)//m=0即代表数组arr1中已经没有元素了，所以中位数从B中找 return B[start2+k-1];//下标加start2的原因是不一定是从下标0开始，可能下标0到start2的元素已经被抛弃 if(k==1) return min(A[start1],B[start2]); int x=min(k/2,m),y=k-x;//记录两组中位数下标 if(A[start1+x-1]<B[start2+y-1]) return findKth(A,B,start1+x,start2,m-x,n,k-x);//start1+x表示舍弃x个不可能的元素，m-x表示将x个元素 //剔除掉数组，k-x表示这x个元素已经被剔除，接下来中位数表示第k-x个元素 else if(A[start1+x-1]>B[start2+y-1]) return findKth(A,B,start1,start2+y,m,n-y,k-y);//start2+y表示舍弃y前的元素 else return A[start1+x-1]; }//本题舍弃的均为各自数组所选下标之前的元素 };Accepted
总耗时: 316 ms 100% 数据通过测试.