a***0
发帖数: 53 | |
j***y
发帖数: 1640 | 2 老夫的粗快猛的 搞法 是， 先 merge 成一个sorted list. 再取中值就容易了。 |
p*****2
发帖数: 21240 | 3 怎么merge？
【在 j***y 的大作中提到】
: 老夫的粗快猛的 搞法 是， 先 merge 成一个sorted list. 再取中值就容易了。
|
l******s
发帖数: 3045 | |
l******s
发帖数: 3045 | 5 O(m*n)的解法吧
【在 p*****2 的大作中提到】
: 怎么merge？
|
T****U
发帖数: 3344 | 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***y
发帖数: 1640 | 7 这样的东西，平时研究研究还可以，临时考别人，我不知道出题的人怎么想的。 |
C******h
发帖数: 786 | 8 这题的前提肯定是不能merge否则太没意思了: )
像lz给的那个网站里给的方法每次去掉各数组中最大median所在数组的后一半元素。效
率比较高。
把这个思路反过来, 比较直接, n个数组最前面的元素比较去掉最小的, 再接着比直到
去掉N/2个元素
【在 j***y 的大作中提到】
: 老夫的粗快猛的 搞法 是， 先 merge 成一个sorted list. 再取中值就容易了。
|
j**********3
发帖数: 3211 | |
a***0
发帖数: 53 | 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的长度
|
c**y
发帖数: 172 | 11 两个难点吧
1。2个变成k个
2。array变成list。sorted array可以O(1)去掉一半，但是sorted list的话没有O(1)
的方法能去掉一半，只能是O(n)。
【在 a***0 的大作中提到】
:
: with-
: 谢谢，感觉帖子里代码的思路和我的是一样的，主要是变成K个list之后问题会复杂很
: 多。。。
|
