l**h
发帖数: 893 | 1 之前看到面经:"n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min
heap的方法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开
销，写了代码。"
min heap的方法容易解释，但是怎么O(1) space合并而时间效率和min heap一样呢？ |
b*****u
发帖数: 648 | 2 heap size n:
mn*logn
heap size k:
mn * log n * log k
（每个数要经历logn次merge）
所以还是同阶 |
l**h
发帖数: 893 | 3 没有太看懂你的
用一个size为n的min heap, 可以达到 mn*logn.
问题是现在只准用O(1) space, 要达到同样的时间效率
【在 b*****u 的大作中提到】
: heap size n:
: mn*logn
: heap size k:
: mn * log n * log k
: （每个数要经历logn次merge）
: 所以还是同阶
|
w****x
发帖数: 2483 | 4 NODE* mergLists(NODE* lsts[], int n)
{
if (lsts == NULL || n <= 0)
return NULL;
while (n > 1)
{
for (int i = 0; i < n; i += 2)
{
if (i+1 >= n)
{
lsts[(n-1)/2] = lsts[i];
break;
}
lsts[i/2] = mergeTwoList(lsts[i], lsts[i+1]);
}
n = (n+1)/2;
}
return lsts[0];
} |
l**h
发帖数: 893 | 5 通过多次两路归并？这个复杂度比min heap要高吧，
假如合并之后的总数据长度为n,
多次两路归并 O(nlog(n))
多路归并(用min heap): O(nlog(k)), k是原始linkedlist个数
【在 w****x 的大作中提到】
: NODE* mergLists(NODE* lsts[], int n)
: {
: if (lsts == NULL || n <= 0)
: return NULL;
: while (n > 1)
: {
: for (int i = 0; i < n; i += 2)
: {
: if (i+1 >= n)
: {
|
b*****u
发帖数: 648 | 6 假设k 是常数。 也就是用一个常数size的heap
这样每轮merge对每个数插入的开销减小了，merge的轮数增多了。但是开销仅仅增大了
logk 倍
【在 l**h 的大作中提到】
: 没有太看懂你的
: 用一个size为n的min heap, 可以达到 mn*logn.
: 问题是现在只准用O(1) space, 要达到同样的时间效率
|
p*****2
发帖数: 21240 | 7 但是怎么O(1) space合并而时间效率和min heap一样呢？
哪里来的这个要求？ |
r*********n
发帖数: 4553 | 8 interesting
are you suggesting double-layer merge?
merge every k lists and then merge n/k items from the previous merge
m*n*lgk*lg(n/k)
but in the second layer of merge, you still need O(n) space
【在 b*****u 的大作中提到】
: 假设k 是常数。 也就是用一个常数size的heap
: 这样每轮merge对每个数插入的开销减小了，merge的轮数增多了。但是开销仅仅增大了
: logk 倍
|
l**h
发帖数: 893 | 9 原题：
http://www.mitbbs.com/article_t/JobHunting/32279127.html
第五轮，n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min heap的方
法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开销，写了
代码。
【在 p*****2 的大作中提到】
: 但是怎么O(1) space合并而时间效率和min heap一样呢？
: 哪里来的这个要求？
|
l**h
发帖数: 893 | 10 原题：
http://www.mitbbs.com/article_t/JobHunting/32279127.html
第五轮，n个排序链表，每个有m个元素，如何合并成一个。最开始说的是min heap的方
法，他要求的是O(1) space但是时间效率一样的，想出来了，然后证明时间开销，写了
代码。
【在 p*****2 的大作中提到】
: 但是怎么O(1) space合并而时间效率和min heap一样呢？
: 哪里来的这个要求？
|
w****x
发帖数: 2483 | 11
嗯，是啊。有道理。
可能面试官自己也搞错了
【在 l**h 的大作中提到】
: 通过多次两路归并？这个复杂度比min heap要高吧，
: 假如合并之后的总数据长度为n,
: 多次两路归并 O(nlog(n))
: 多路归并(用min heap): O(nlog(k)), k是原始linkedlist个数
|
