2个有序数组求合并后的中位数
这里作者并没有证明为什么两个各取子不同数组的子数组合并起来的中位数,仍然是两个数组的中位数,现在证明: 设两个数组的下边分别是X[i1,j1]和Y[i2,j2],m1=(i1+j1)/2,m2=(i2+j2)/2, 可知m1+m2=i2+j1=i1+j2, 当X[m1]=Y[m2]的情况就不说了。 下面来看当X[m1]<X[m2]的时候,设median' 是X[m1......j1]和Y[i2......m2]的中位数,则medina=media' 事实上,对任意的i1=<i<=m1有X[i]<=X[m1]<=median'。对于任意m2<j<=j2有Y[j]>=Y[m2]>=median‘,即median'为X[i1......j1]和Y[m2.....j2]中位数,即median=median'(注意media和median'可能代表2个数)。这里需要解释一下,根据中位数的定义,只要median'有n或者n-1个比它小的数,有n或者n-1一个比它大的数,我们就叫这个median'为整个数组的中位数,因为median'是Y[i2.....m2]和X[m1.....j1]的中位数,所以median'前面一定有(m2-i2+1)或者(m2-i2)个比它小的数,由于i1=<i<=m1有X[i]<=X[m1]<=median'所以,median'前面也有n或者n-1个比它小的数,根据中位数定义可知,media'=median(注意media和median'可能代表2个数)括号里我的理解不是很清晰,我也整不出来,但感觉它说的是对的!
解析: 这个题目看起来非常简单。第一题的话: 假设数组长度为n, 那么我就把数组1和数组2直接合并,然后再直接找到中间元素。对于这样的方案,第一题和第一题就没有什么区别了。这样的话时间复杂度就是O(n)。通常在这样的情况下,那些mentor类型的达人就会循循善诱道:“你还有更好的办法吗:)” 如果比线性更高效,直接能想到的就是对数了O(log(n)),这个时间复杂度在这里可能吗? 当然还是可能的。来继续看看下面的分析。 先找来了一个图(自己画的,简陋了点) 我们先来分析看看: 想到对数的效率,首先想到的就是二分查找,对于这个题目二分查找的意义在哪里呢? 我们找到了A[n/2] 和 B[n/2]来比较, 如果他们相等,那样的话,我们的搜索结束了,因为答案已经找到了A[n/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]里面找到合并以后的中位数, 显然递归是个不错的选择了。 类似的, 如果B[n/2]<A[n/2]呢?显然就是在A[0]-A[n/2]和B[n/2]-B[n]里面寻找了。 在继续想, 这个递归什么时候收敛呢?当然一个case就是相等的值出现, 如果不出现等到这个n==1的时候也就结束了。 照着这样的思路, 我们比较容易写出如下的代码, 当然边界的值需要自己思量一下, 前面的想法只是想法而已。 马上有人说那不定长的怎么办呢?一样的,我们还是来画个图看看:(我的画图水平肯定提高了)
一样的, 我们还是把这个两个数组来比较一下,不失一般性,我们假定B数组比A数组长一点。A的长度为n, B的长度为m。比较A[n/2]和B[m/2] 时候。类似的,我们还是分成几种情况来讨论: a. 如果A[n/2] == B[m/2],那么很显然,我们的讨论结束了。A[n/2]就已经是中位数,这个和他们各自的长度是奇数或者偶数无关。 b. 如果A[n/2] < B[m/2],那么,我们可以知道这个中位数肯定不在[A[0],A[n/2])这个区间内,同时也不在[B[m/2],B[m]]这个区间里面。这个时候,我们不能冲动地把[A[0],A[n/2])和[B[m/2],B[m]]全部扔掉。我们只需要把[B[m-n/2],B[m]]和[A[0],A[n/2])扔掉就可以了。(如图所示的红色线框),这样我们就把我们的问题成功转换成了如何在A[n/2]->A[n]这个长度为n/2的数组和B[1]-B[m-n/2]这个长度为m-n/2的数组里面找中位数了。问题复杂度即可下降了。 c. 只剩下A[n/2] > B[m/2],和b类似的,我们可以把A[n/2]->A[n]这块以及B[1]->B[n/2]这块扔掉了就行,然后继续递归。 我们也可以写下如下的代码:
在一些特定的case下面测试了一下,结果还是正确的,下面是用的testcase:
|
|