o*z
发帖数: 1078 | 1 如何sort and merge n 个sorted linked list？
假设n 很大，比如million, 用什么结构和方法优化？ | c**********e
发帖数: 2007 | 2 Can you merge by subgroup, say merge every 2 first? | r********n
发帖数: 7441 | 3 some thoughts based on branch and bound method: recursion + divide and conquer + merge sort
i) pick a number a, then divide n sorted linked lists into three classes:
1. min(list elements) > a
2. max(list elements) < a
3. remaining lists
ii) create three branches for them: L, M, R, if any branch contains <= 3
lists, perform merge sort, make the branch as fathomed
iii) pick any unfathomed node, perform i) ~ iii)
【在 o*z 的大作中提到】
: 如何sort and merge n 个sorted linked list？
: 假设n 很大，比如million, 用什么结构和方法优化？
| h******3
发帖数: 3 | | h******3
发帖数: 3 | 5 二楼的办法 time = O(M*log(n)) 假设n个sorted list，一共M个element。
因为 merge 两个sorted list 是 linear time。 而每个element会被merge log（n）
次。
三楼的办法 best case 是 O(M*log(n)) 。 average case可能要差很多。因为分区不
均匀。
内存都是 O(M） | M**u
发帖数: 10158 | 6 map reduce
【在 o*z 的大作中提到】
: 如何sort and merge n 个sorted linked list？
: 假设n 很大，比如million, 用什么结构和方法优化？
|
|
