上海建站模板搭建,中国钓鱼网站大全,惠州网站建设(推荐乐云践新),wordpress数据盘问题分析
先建立一个小顶堆将每一路的最小元素都加入小顶堆#xff0c;此时堆顶元素就是全局的最小值将堆顶元素弹出。若堆顶元素所在的数组不为空#xff0c;则将下一元素加入堆中重复2、3操作#xff0c;直到所有数据都读取完毕将堆内元素按顺序读出#xff0c;并清空堆…问题分析
先建立一个小顶堆将每一路的最小元素都加入小顶堆此时堆顶元素就是全局的最小值将堆顶元素弹出。若堆顶元素所在的数组不为空则将下一元素加入堆中重复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(vectorListNode* lists) {// 最小堆auto cmp [](const ListNode* A, const ListNode* B) {return A - val B - val;};priority_queueListNode*, vectorListNode*, 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;}
};
