W********e
发帖数: 45 | 1 我的办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表
集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
应该是O(n)。
我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
class Solution {
public:
ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
{
ListNode *h1=l1,*h2=l2;
ListNode *newHead=new ListNode(0),*dummy=newHead; //newHead要赋
值，否则没有next。如果是C语言的话可以申请stack的对象
if(l1==NULL&&l2==NULL)
return NULL;
while(h1!=NULL&&h2!=NULL)
{
if(h1->val>=h2->val)
{
dummy->next=h2;
dummy=h2;
h2=h2->next;
}
else
{
dummy->next=h1;
dummy=h1;
h1=h1->next;
}
}
if(h1==NULL)
dummy->next = h2;
else if(h2==NULL)
dummy->next= h1;
return newHead->next;
}
ListNode *mergeKLists(vector &lists) {
if(lists.size() == 0)
return NULL;
int curSize = lists.size();
while(curSize > 1) {
int halfSize = (1 + curSize) / 2;
//merge i,i + halfSize
for(int i = 0 ; i < halfSize && i + halfSize < curSize; ++i) {
ListNode *first = lists[i];
ListNode *second = lists[i + halfSize];
ListNode *result = mergeSortedList(first,second);
lists[i] = result;
}
//set curSize to halfsize
curSize = halfSize;
}
return lists[0];
}
}; |
p*****p
发帖数: 379 | 2 new完没有delete
复杂度不对
用heap就行了，其他纯属吃力不讨好
【在 W********e 的大作中提到】
: 我的办法就是进行二分，将k个链表分为两个一组，组内进行merge。形成一个新的链表
: 集合。继续两个一组merge，这样下去一共会进行logk次merge，最后merge成为一个链
: 表。这里用的辅助函数是mergeSortedList，合并两个有序链表，这个辅助函数复杂度
: 应该是O(n)。
: 我觉得这个算法的总时间复杂度是O(nlogK),大家觉得对吗？？
: class Solution {
: public:
: ListNode* mergeSortedList(ListNode*l1,ListNode*l2)
: {
: ListNode *h1=l1,*h2=l2;
|
W********e
发帖数: 45 | 3
哦对没有delete。我用C语言写面试题，用heap感觉不太方便啊，怎么办？
【在 p*****p 的大作中提到】
: new完没有delete
: 复杂度不对
: 用heap就行了，其他纯属吃力不讨好
|
p*****p
发帖数: 379 | 4 当场写白板你可以说假设有heap这么个容器，对方不同意的话就写个heapify函数好了
，我感觉当场写的话这些halfSize要一下搞对也不容易啊……
而且你都用了new了……C++有priority_queue的STL
【在 W********e 的大作中提到】
:
: 哦对没有delete。我用C语言写面试题，用heap感觉不太方便啊，怎么办？
|
n*****g
发帖数: 178 | 5 纯属好奇问问，楼主的复杂度应该是多少？
【在 p*****p 的大作中提到】
: new完没有delete
: 复杂度不对
: 用heap就行了，其他纯属吃力不讨好
|
r*********n
发帖数: 4553 | 6 用indexed priority queue（其实就是heap，但是不需要自己写，除非面馆要求）或者
一般的priority queue，但是进去的是pair，然后overwrite operator<
for pair，pair的第二个是list index。
【在 W********e 的大作中提到】
:
: 哦对没有delete。我用C语言写面试题，用heap感觉不太方便啊，怎么办？
|
l*******b
发帖数: 2586 | 7 ListNode *mergeKLists(vector &lists) {
if(lists.empty())
return NULL;
int n = lists.size();
while(n > 1) {
int i;
for(i = 0; i < n/2; ++i)
lists[i] = mergeTwoList(lists[2*i], lists[2*i+1]);
if(n % 2) {
lists[i] = lists[n-1];
n = n/2 + 1;
} else
n = n/2;
}
return lists[0];
}
ListNode *mergeTwoList(ListNode *s, ListNode *t) {
ListNode *h, **c = &h;
while(s && t) {
if(s->val < t->val) {
*c = s;
s = s->next;
} else {
*c = t;
t = t->next;
}
c = &(*c)->next;
}
if(s)
*c = s;
else
*c = t;
return h;
} |
p*****p
发帖数: 379 | 8 我认为是Nk
跟逐个合并是一回事
【在 n*****g 的大作中提到】
: 纯属好奇问问，楼主的复杂度应该是多少？
|
Y**3
发帖数: 21 | 9
可以用C++算法库里的heap操作make_heap,push_heap等
【在 W********e 的大作中提到】
:
: 哦对没有delete。我用C语言写面试题，用heap感觉不太方便啊，怎么办？
|
l*********8
发帖数: 4642 | 10 NlogK吧
【在 p*****p 的大作中提到】
: 我认为是Nk
: 跟逐个合并是一回事
|
|
|
p*****p
发帖数: 379 | 11 为啥？不是一共合并了1 + 2 + 4 + 8 + ... + k / 2次么？
【在 l*********8 的大作中提到】
: NlogK吧
|
l*********8
发帖数: 4642 | 12 对，楼主的算法是NK。 我以为说的是用heap的算法， 看错了。
【在 p*****p 的大作中提到】
: 为啥？不是一共合并了1 + 2 + 4 + 8 + ... + k / 2次么？
|
l*********8
发帖数: 4642 | 13 对，楼主的算法是NK。 我以为说的是用heap的算法， 看错了。
【在 p*****p 的大作中提到】
: 为啥？不是一共合并了1 + 2 + 4 + 8 + ... + k / 2次么？
|
d********r
发帖数: 38 | 14 NLogK, N is the total number of elements in K lists
Merging two lists with length N1 and N2 is O(N1+N2)
So the first round of k/2 merges totally took O(N) time
So as the second round, etc.
The total number of rounds is LogK, so O(NlogK). |
l*********8
发帖数: 4642 | 15 对。 我刚才是怎么想的。。。。
【在 d********r 的大作中提到】
: NLogK, N is the total number of elements in K lists
: Merging two lists with length N1 and N2 is O(N1+N2)
: So the first round of k/2 merges totally took O(N) time
: So as the second round, etc.
: The total number of rounds is LogK, so O(NlogK).
|
W********e
发帖数: 45 | 16
我赞同。
【在 d********r 的大作中提到】
: NLogK, N is the total number of elements in K lists
: Merging two lists with length N1 and N2 is O(N1+N2)
: So the first round of k/2 merges totally took O(N) time
: So as the second round, etc.
: The total number of rounds is LogK, so O(NlogK).
|
