A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 King_L 于 2014-9-20 15:27 编辑

两个等大小有序数组,怎样才能找出他们的中间值?

点评

在得到答案后如果没有把问题设为提问结束是得不到技术分的哦。这次破例  发表于 2014-9-19 22:24

评分

参与人数 1技术分 +1 收起 理由
陈君 + 1

查看全部评分

12 个回复

倒序浏览
折半查找,思考一下试试
回复 使用道具 举报
Minemineㄟ无心 发表于 2014-9-19 10:39
折半查找,思考一下试试

效率太低了。
回复 使用道具 举报

什么叫“等大小有序数组”、“等大小有序数组的中间值”?举个具体例子?
回复 使用道具 举报
fantacyleo 发表于 2014-9-19 12:17
什么叫“等大小有序数组”、“等大小有序数组的中间值”?举个具体例子? ...

数组长度相等,而且两个数组都是排好序的。
回复 使用道具 举报
King_L 发表于 2014-9-19 14:31
数组长度相等,而且两个数组都是排好序的。

那什么叫“他们的中间值”?比如{1,2,3,5} 和{4,6,7,9},怎么算中间值?
回复 使用道具 举报
King_L 中级黑马 2014-9-19 14:58:58
7#
fantacyleo 发表于 2014-9-19 14:35
那什么叫“他们的中间值”?比如{1,2,3,5} 和{4,6,7,9},怎么算中间值?

你可以想像成是奇数的数组。我描述的就是当时面试官问我的。他就是那么问的。别的什么都没说。所以我也不太清楚。
回复 使用道具 举报
King_L 发表于 2014-9-19 14:58
你可以想像成是奇数的数组。我描述的就是当时面试官问我的。他就是那么问的。别的什么都没说。所以我也不 ...

。。。。。。你说分奇偶,我似乎有点明白了,实际上是要找两个数组合并后,也就是{1 2 3 4 5 6 7 9}的中位数?
回复 使用道具 举报
King_L 中级黑马 2014-9-20 09:46:23
9#
fantacyleo 发表于 2014-9-19 15:01
。。。。。。你说分奇偶,我似乎有点明白了,实际上是要找两个数组合并后,也就是{1 2 3 4 5 6 7 9}的中 ...

大概是的
回复 使用道具 举报

嗯,这样的话不难。因为两个数组分别有序,那就可以仿照归并排序的合并阶段,将2个有序数组合并为新的有序数组,然后取中间下标的元素即可,时间复杂度是O(n),n为2个数组的长度。
回复 使用道具 举报
fantacyleo 发表于 2014-9-20 11:51
嗯,这样的话不难。因为两个数组分别有序,那就可以仿照归并排序的合并阶段,将2个有序数组合并为新的有 ...

如果不合并呢?
回复 使用道具 举报
King_L 发表于 2014-9-20 15:00
如果不合并呢?

当然没有必要完全合并,因为每个数组长度是k,那么合并到第k个数即可,它就是所求的中间值了
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马