首页 诗词 字典 板报 句子 名言 友答 励志 学校 网站地图
当前位置: 首页 > 教程频道 > 开发语言 > 编程 >

无序数组A跟B,线性时间复杂度,空间复杂度O(1) ,求中位数

2012-11-11 
无序数组A和B,线性时间复杂度,空间复杂度O(1) ,求中位数两个无序数组A和B,长度分别是m和n,求中位数,要求时

无序数组A和B,线性时间复杂度,空间复杂度O(1) ,求中位数

两个无序数组A和B,长度分别是m和n,求中位数,要求时间复杂度O(m+n),空间复杂度O(1) 

来自:人人网面试题,5分钟出思路,10分钟出代码

分析:乍一看题目,不知道在考什么。

把问题简化下。有一个无序数组,长度m+n,在O(m+n)时间内找出中位数,空间复杂度O(1)。

可以用快速查找在线性时间里找出中位数。

若分布在两个数组里,该怎么找?

是否可以把两个数组看成是一个,当查找到数组边界时,做一次边界判断,跳到另一个数组继续查找。

判断起来有点麻烦,但应该可以实现。欢迎讨论

热点排行