首页 > 试题广场 >

2个有序数组，长度为n，查找两个数组整体中值（中值：一组数组

[问答题]
2个有序数组，长度为n，查找两个数组整体中值（中值：一组数组中居中的数），复杂度是（）？用（）方法？
查看答案及解析
添加回答
Hefa头像 Hefa
时间复杂度O（logn）
方法如下：
（1）取所有数组的最小值和最大值，求出全体的最大值和最小值min max然后取m=(min+max)/2
（2）用m在所有数组中搜索,找到比m小的数的个数n1,若n1大于M*N/2，则mid=(min+mid)/2，否则mid=(mid+max)/2
（3）重复上述搜索一共循环log(max-min)次
发表于 2014-10-25 00:26:14 回复(0)
提交观点

问题信息

数组 复杂度 阿里巴巴
上传者：Rebecca
难度：
1条回答 3015浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号