forked from keon/algorithms
-
Notifications
You must be signed in to change notification settings - Fork 12
/
merge_sorted_k_lists.py
63 lines (49 loc) · 1.83 KB
/
merge_sorted_k_lists.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
"""
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
"""
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
from heapq import heappush, heappop, heapreplace, heapify
def mergeKLists(lists):
dummy = node = ListNode(0)
h = [(n.val, n) for n in lists if n]
heapify(h)
while h:
v, n = h[0]
if n.next is None:
heappop(h) #only change heap size when necessary
else:
heapreplace(h, (n.next.val, n.next))
node.next = n
node = node.next
return dummy.next
from Queue import PriorityQueue
def merge_k_lists(lists):
dummy = ListNode(None)
curr = dummy
q = PriorityQueue()
for node in lists:
if node: q.put((node.val,node))
while q.qsize()>0:
curr.next = q.get()[1]
curr=curr.next
if curr.next: q.put((curr.next.val, curr.next))
return dummy.next
"""
I think my code's complexity is also O(nlogk) and not using heap or priority queue,
n means the total elements and k means the size of list.
The mergeTwoLists functiony in my code comes from the problem Merge Two Sorted Lists
whose complexity obviously is O(n), n is the sum of length of l1 and l2.
To put it simpler, assume the k is 2^x, So the progress of combination is like a full binary tree,
from bottom to top. So on every level of tree, the combination complexity is n,
beacause every level have all n numbers without repetition.
The level of tree is x, ie logk. So the complexity is O(nlogk).
for example, 8 ListNode, and the length of every ListNode is x1, x2,
x3, x4, x5, x6, x7, x8, total is n.
on level 3: x1+x2, x3+x4, x5+x6, x7+x8 sum: n
on level 2: x1+x2+x3+x4, x5+x6+x7+x8 sum: n
on level 1: x1+x2+x3+x4+x5+x6+x7+x8 sum: n
"""