Median of Two Sorted Arrays [leetcode 4]

Median of Two Sorted Arrays

求两个有序数组的中位数的题,以前想了很久,没搞定,后来再看,发现原来很简单。

主要还是二分的思想,但是不能做到严格意义log(m+n),只是统计意义上的log(m+n);

想法很简单,就是在第一个数组中找到当前的中位数,然后在第二个数组中log(N)查找位置,看这个数字距离真正的中位数是大了,还是小了,如果小了,好,那所有小于这个数字的数都排除掉,更新待查找的区间,然后重新找新区间中位数,再次对比距离真正中位数的距离。

首先确定两个变量,max1,min1,表示第一个数组的未被排除区间,min2,max2表示第二个数组的未被排除区间。left,right 表示仍需要排除的的数字大小,中位数,也就是这个数字的左边有一半小于它的数需要去掉,右边有一半大于它的书去掉,剩下的,就是真正的中位数。所以当left = 0 的时候,也即是目前剩下的最小的,因为比它小的一半,刚刚好被去掉完了。剩下的就是了。

思想是这样的,真正处理的时候,就需要考虑很多特殊情况,因为两个数组,是没有办法把全部的数都排除,然后剩下的刚刚就是想要的,所以当有一个数组,剩下只有一个或者两个的时候,就停止排除,然后合并数组,从其中找到我们想要的数字,根据left和right可以轻松做到这一点。

代码连结如下:

https://github.com/unasm/utils/blob/test/4.c

Leave a comment

Your email address will not be published.

*