Merge k Sorted Lists
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
分析
设总长度为n。
最简单的办法就是扫一遍k个链表的开头,哪个最小就把它移除,加入到结果链表中。这样时间复杂度是kn
第二个办法就是进行二分,将k个链表分为两个一组,组内进行merge。形成一个新的链表集合,大小为(k + 1)/2。继续两个一组merge,这样下去一共会进行logk次merge,最后merge成为一个链表。总的时间复杂度是nlogk
其中两个list合并的代码同LeetCode题目:Merge Two Sorted Lists
代码:72ms过大集合
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) { ListNode *proot = NULL; ListNode **pplast = &proot; while(l1 || l2){ if(l1) { ListNode *minNode; if(!l2 || l1->val <= l2->val){ //l1 is min minNode = l1; l1 = l1->next; } else if(l2) { //l2 is min minNode = l2; l2 = l2->next; } //proceed root *pplast = minNode; pplast = &(minNode->next); } else { //l1 is empty *pplast = l2; break; } } return proot; } 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 = mergeTwoLists(first,second); lists[i] = result; } //set curSize to halfsize curSize = halfSize; } return lists[0]; } };
假如用n来表示单个数组长度:
第一种情况下是O(k*(k*n)) ,因为一共要添加k*n个节点,而添加每个需要的是k次比较;
第二种情况下是O(k*n);
差不多是这样的吧。
第二种按照你的n定义,应该是O(nklogk),你可以实际计算一下时间复杂度。
分组merge的复杂度并不是n*logk
因为随着每次merge数组长度增加 复杂度不再是O(2n)了
而是O(4n), O(8n), … 一共大概有logk项的等比数列
最后结果应该还是O(n*k)
恩,是的。
第二种方法的时间复杂度还是O(n log k).
http://stackoverflow.com/questions/2705366/merging-k-sorted-linked-lists-analysis
每次merge的时间复杂度是随merge的两个list的长度线性增长的。
分析貌似不对。。。
kn+(k-1)n+(k-2)n+…
=o(kn^2)
not kn.
针对第一种方法,我假设总长度是n,那么对于每个加到结果链表中的节点,需要扫一遍k个list找到前端最小的那一个节点(这次扫描是O(k)),那么n个节点总共需要O(n*k)的。