多路归并
若为$k$路归并,每次选出一个元素需要$O(1)$,插入新元素需要$O(logk)$,时间复杂度为$O(Nlogk)$。
// 重载括号
struct Cmp{
bool operator()(ListNode* a, ListNode* b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 小根堆
priority_queue<ListNode*, vector<ListNode*>, Cmp> heap;
auto dummy = new ListNode(-1);
auto tail = dummy;
for(auto h: lists) if(h) heap.push(h);
while(heap.size()) {
auto t = heap.top();
heap.pop();
if(t->next) heap.push(t->next);
tail->next = t;
tail = tail->next;
}
return dummy->next;
}
};
C++11泛型写法
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 小根堆
auto cmp = [](ListNode* a, ListNode* b){return a->val > b->val;};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> heap(cmp);
auto dummy = new ListNode(-1);
auto tail = dummy;
for(auto h: lists) if(h) heap.push(h);
while(heap.size()) {
auto t = heap.top();
heap.pop();
if(t->next) heap.push(t->next);
tail->next = t;
tail = tail->next;
}
return dummy->next;
}
};