问题分析
- 先建立一个小顶堆
- 将每一路的最小元素都加入小顶堆,此时堆顶元素就是全局的最小值
- 将堆顶元素弹出。若堆顶元素所在的数组不为空,则将下一元素加入堆中
- 重复2、3操作,直到所有数据都读取完毕
- 将堆内元素按顺序读出,并清空堆内元素
复杂度分析
建堆操作的时间复杂度: O ( l o g k ) O(logk) O(logk)
- 递归式: T ( k ) = 2 T ( k / 2 ) + l o g n T(k) = 2T(k/2) + logn T(k)=2T(k/2)+logn,可以用主定理得出上述建堆操作的时间复杂度
单次插入操作的时间复杂度: O ( l o g k ) O(logk) O(logk)
返回堆顶元素的时间复杂度: O ( 1 ) O(1) O(1)
删除堆顶元素的时间复杂度: O ( l o g k ) O(logk) O(logk)
整体的时间复杂度: O ( n l o g k ) O(nlogk) O(nlogk)
程序代码
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 最小堆
auto cmp = [](const ListNode* A, const ListNode* B) {
return A -> val > B -> val;
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> q;
// 初始化小顶堆
for(int i = 0; i < lists.size(); i++) {
if( lists[i] ) q.push(lists[i]);
}
ListNode* dummy = new ListNode();
ListNode* head = dummy;
while( !q.empty() ) {
auto node = q.top();
q.pop();
head -> next = node;
if( node -> next ) {
node = node -> next;
q.push(node);
}
head = head -> next;
}
return dummy -> next;
}
};