• 解题:两数组中位数[难度难]

    2015/10/31 JSRGFJZ

题目:

给出两个数组,其长度分别为m,n,请找出两数组的中位数。时间复杂度为0(m+n)

示例:

(木有示例)

思路:

首先第一个思路就是先merge,然后找中位数。但时间复杂度为0(m+n)就是二分法了。

本题的一个核心思路就是:假设m大于k/2,我先找到第k/2个,设为a,剩下的第k/2个设为b,

如果a小于b,那么把整个数组merge的话,第一个数组的前k/2个,也就是说,到第k/2个在排序merge之后也是前面的,之后的寻找是没有作用的。

如果a小于b,同样的思路;

如果a等于b,返回其中一个。

代码:

 

1 收藏


直接登录