[LeetCode]Median of Two Sorted Arrays

干了好几天LeetCode,也艹了50+题了,上面一些题还是不错的,未免以后越做越多,然后越不想把一些好的题给找出来,这里先停停记录几个好题。我在github上建了一个repository(点这里),把我的代码公开,欢迎fork加star。(哦对了,是python代码,顺便当练习python)

这个题是找两个已排序序列合并后的中位数,要注意如果两序列总长是偶数的话,中位数是取中间两个数的平均值。

普通方法当然可以先合并两个序列,然后直接得到中位数。但是合并的过程是O(m+n)的,显然效率不够高,所以要想别的算法。

细想一下这个题可以看成是找两已排序序列的第k小数的一个特殊情况,这里k=[(m+n)/2],偶数的话再求一个第k+1小然后求平均。求什么第k小的很容易想到快排那一套,先找到一个值,能够知道比它小的有几个比它大的有几个,然后递归去剩下的子序列中求解。这里是2个序列,而且是已排序的,那就得变个法。下面是讨论如何求第k小数

不妨假设两个序列长都是偶数。首先找到两个序列各自的中间值(位于上半部分的),其中一个值为a,另一个值为b,如图:图1

第一种情况:如果a=b,那说明两序列排序之后,肯定a上面的和b上面的在前面,然后是a和b,然后是各自下面的。那么如果k<= (m+n)/2的话,说明第k小数是两个序列上半部分合并形成的序列中的第k小数,于是算法递归在两序列上半部分去找第k小数。否则在两序列下半部分去找。

第二种情况:如果a<b,那么至少确定右边序列的下半部分至少要大于(m+n)/2个数。所以如果k<=m/2,那么只要在两序列的各自上半部分去找第k小数就行了,因为两序列的下半部分都至少要大于m/2个数。如果k>(m+n)/2,能够确定第k小数绝对不可能在左边序列的上半部分,因为这部分既比下半部分小,又肯定比右边序列的下半部分小,还至少比右边序列的上半部分的一个小(b)。所以可以排除m/2个元素,对左边序列的下半部分和右边序列递归的找第k-m/2小数。否则,因为右边序列的下半部分至少大于(m+n)/2个数,所以肯定第k小数不在这个部分,于是递归的在左边序列和右边序列上半部分去找。

实际过程也要注意一个序列为空的情况(那就直接在另一个序列找第k小数),还有实际序列长度会为奇数,注意导致死循环的情况。

代码见我的github。



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*