求代码，median of K sorted list - 未名空间MITBBS历史存档

求代码，median of K sorted list

求代码，median of K sorted list# JobHunting - 待字闺中

a*02015-08-23 07:08

1 楼

看了网上的一些文章，思路大概有，但觉得细节实在太多了，所以想找个程序参考一下
。。
我是参考的这篇文章，但实现起来好复杂。。
https://algnotes.wordpress.com/2010/05/30/finding-median-in-3-arrays/

j*y2015-08-23 07:08

2 楼

老夫的粗快猛的搞法是，先 merge 成一个sorted list. 再取中值就容易了。

p*22015-08-23 07:08

3 楼

怎么merge？

【在 j***y 的大作中提到】

: 老夫的粗快猛的搞法是，先 merge 成一个sorted list. 再取中值就容易了。

l*s2015-08-23 07:08

4 楼

想做成O(m*lgm*lgn)超级烦，我放弃了

l*s2015-08-23 07:08

5 楼

O(m*n)的解法吧

【在 p*****2 的大作中提到】

: 怎么merge？

T*U2015-08-23 07:08

6 楼

参考这个
https://leetcode.com/discuss/17815/share-one-divide-conquer-log-method-with-
clear-description
divide and conquer
加一个heap, 每次去掉一个list的一半，可以做到nlognlogm, n为list数量，m为最长
list的长度

【在 a***0 的大作中提到】

: 看了网上的一些文章，思路大概有，但觉得细节实在太多了，所以想找个程序参考一下
: 。。
: 我是参考的这篇文章，但实现起来好复杂。。
: https://algnotes.wordpress.com/2010/05/30/finding-median-in-3-arrays/

j*y2015-08-23 07:08

7 楼

这样的东西，平时研究研究还可以，临时考别人，我不知道出题的人怎么想的。

C*h2015-08-23 07:08

8 楼

这题的前提肯定是不能merge否则太没意思了: )
像lz给的那个网站里给的方法每次去掉各数组中最大median所在数组的后一半元素。效
率比较高。
把这个思路反过来, 比较直接, n个数组最前面的元素比较去掉最小的, 再接着比直到
去掉N/2个元素

【在 j***y 的大作中提到】

: 老夫的粗快猛的搞法是，先 merge 成一个sorted list. 再取中值就容易了。

j*32015-08-23 07:08

9 楼

mark

a*02015-08-23 07:08

10 楼

with-
谢谢，感觉帖子里代码的思路和我的是一样的，主要是变成K个list之后问题会复杂很
多。。。

【在 T****U 的大作中提到】

: 参考这个
: https://leetcode.com/discuss/17815/share-one-divide-conquer-log-method-with-
: clear-description
: divide and conquer
: 加一个heap, 每次去掉一个list的一半，可以做到nlognlogm, n为list数量，m为最长
: list的长度