有序数组求中位数问题

《有序数组求中位数问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、1、有两个已排好序的数组A和B，长度均为n，找出这两个数组合并后的中间元素，要求时间代价为O(logn)。2、假设两个有序数组长度不等，同样的求出中位数。一：解析：这个题目看起来非常简单。第一题的话：假设数组长度为n,那么我就把数组1和数组2直接合并，然后再直接找到中间元素。对于这样的方案，第一题和第一题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下，那些要求比较高的面试官就会循循善诱道：“你还有更好的办法吗？”如果比线性更高效，直接能想到的就是对数了O(log(n))，这个时间复杂度在这里可能吗？当然还是可能的。算法导论上面的分析是这样的：Saythet

2、woarraysaresortedandincreasing,namelyAandB.ItiseasytofindthemedianofeacharrayinO(1)time.AssumethemedianofarrayAismandthemedianofarrayBisn.Then，1、Ifm==n，thenclearlythemedianaftermergingisalsom，thealgorithmholds.2、Ifm<=n，thenreservethehalfofsequenceAinwhichallnumbersaregreaterthanm，alsoreserve

3、thehalfofsequenceBinwhichallnumbersaresmallerthann.Runthealgorithmonthetwonewarrays。3、Ifm>n，thenreservethehalfofsequenceAinwhichallnumbersaresmallerthanm，alsoreservethehalfofsequenceBinwhichallnumbersarelargerthann.Runthealgorithmonthetwonewarrays。Timecomplexity:O(logn)下面，我们来画个图，分析一下这个思路：我们先

4、来分析看看：想到对数的效率，首先想到的就是二分查找，对于这个题目二分查找的意义在哪里呢？我们找到了A[n/2]和B[n/2]来比较，1、如果他们相等，那样的话，我们的搜索结束了，因为答案已经找到了A[n/2]就肯定是排序后的中位数了。2、如果我们发现B[n/2]>A[n/2]，说明什么，这个数字应该在A[n/2]->A[n]这个序列里面，或者在B[1]-B[n/4]这里面。或者，这里的或者是很重要的，我们可以说，我们已经成功的把问题变成了在排序完成的数组A[n/2]-A[n]和B[0]-B[n/2]里面找到合并以后的中位数，显然递归是个不错的选择了。3、如果B[n/2]

5、/2]呢？显然就是在A[0]-A[n/2]和B[n/2]-B[n]里面寻找了。在继续想，这个递归什么时候收敛呢？当然一个case就是相等的值出现，如果不出现等到这个n==1的时候也就结束了。照着这样的思路，我们比较容易写出如下的代码，当然边界的值需要自己思量一下（递归代码如下）：//两个长度相等的有序数组寻找中位数intFind_Media_Equal_Length(inta[],intb[],intlength){if(length==1){returna[0]>b[0]?b[0]:a[0];}intmid=(length-1)/2;//奇数就取中间的，偶数则去坐标小的if(

6、a[mid]==b[mid])returna[mid];elseif(a[mid]

7、Length(a,b+length-mid-1,mid+1);}}非递归代码如下：//非递归代码intFind_Media_Equal_Length(inta[],intb[],intlength){intmid;while(1){if(length==1){returna[0]>b[0]?b[0]:a[0];}mid=(length-1)/2;if(a[mid]==b[mid])returna[mid];elseif(a[mid]