黑马程序员技术交流社区

标题: 两个等大小有序数组，怎样才能找出他们的中间值？ [打印本页]

---

作者: King_L    时间: 2014-9-19 10:37
标题: 两个等大小有序数组，怎样才能找出他们的中间值？


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

---

作者: Minemineㄟ无心    时间: 2014-9-19 10:39
折半查找，思考一下试试

---

作者: King_L    时间: 2014-9-19 10:44

Minemineㄟ无心 发表于 2014-9-19 10:39
折半查找，思考一下试试

效率太低了。

---

作者: fantacyleo    时间: 2014-9-19 12:17

King_L 发表于 2014-9-19 10:44
效率太低了。

什么叫“等大小有序数组”、“等大小有序数组的中间值”？举个具体例子？

---

作者: King_L    时间: 2014-9-19 14:31

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

数组长度相等，而且两个数组都是排好序的。

---

作者: fantacyleo    时间: 2014-9-19 14:35

King_L 发表于 2014-9-19 14:31
数组长度相等，而且两个数组都是排好序的。

那什么叫“他们的中间值”？比如{1,2,3,5} 和{4,6,7,9}，怎么算中间值？

---

作者: King_L    时间: 2014-9-19 14:58

fantacyleo 发表于 2014-9-19 14:35
那什么叫“他们的中间值”？比如{1,2,3,5} 和{4,6,7,9}，怎么算中间值？

你可以想像成是奇数的数组。我描述的就是当时面试官问我的。他就是那么问的。别的什么都没说。所以我也不太清楚。

---

作者: fantacyleo    时间: 2014-9-19 15:01

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

。。。。。。你说分奇偶，我似乎有点明白了，实际上是要找两个数组合并后，也就是{1 2 3 4 5 6 7 9}的中位数？

---

作者: King_L    时间: 2014-9-20 09:46

fantacyleo 发表于 2014-9-19 15:01
。。。。。。你说分奇偶，我似乎有点明白了，实际上是要找两个数组合并后，也就是{1 2 3 4 5 6 7 9}的中 ...

大概是的

---

作者: fantacyleo    时间: 2014-9-20 11:51

King_L 发表于 2014-9-20 09:46
大概是的

嗯，这样的话不难。因为两个数组分别有序，那就可以仿照归并排序的合并阶段，将2个有序数组合并为新的有序数组，然后取中间下标的元素即可，时间复杂度是O(n)，n为2个数组的长度。

---

作者: King_L    时间: 2014-9-20 15:00

fantacyleo 发表于 2014-9-20 11:51
嗯，这样的话不难。因为两个数组分别有序，那就可以仿照归并排序的合并阶段，将2个有序数组合并为新的有 ...

如果不合并呢？

---

作者: fantacyleo    时间: 2014-9-20 15:24

King_L 发表于 2014-9-20 15:00
如果不合并呢？

当然没有必要完全合并，因为每个数组长度是ｋ，那么合并到第ｋ个数即可，它就是所求的中间值了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2