[LeetCode]Merge k Sorted Lists

代码请狂戳这里

题意:有K条已排好序的单链表,要求合并成一个单链表。

2根单链表情况的升级版。最开始的想法当然是取每一根链表的头元素,然后取其中一个最小值,插入到新的单链表中,同时更新这个最小值所在的链表,使其头指针指向下个节点。那么这里怎么找最小值?普通的线性查找当然可以,但是复杂度太大,寻找最小值需要O(k),那么整个算法的复杂度就是O(kn),不行。那么怎么办?当然是用堆。

记录这个题倒不是因为这个题难,当然经典确实经典,主要是因为学到了python中的堆操作,真是爽的一[哔——]啊!这里主要写下基本的用法,具体看这里

heap是一个列表(数组)。

heapq.heapify(heap) #如果这个列表是初始的,要把它变成堆结构,那么调用这个函数
heapq.heappush(heap,item) #把item加入到堆中
heapq.heappop(heap) #弹出heap中的最小值,也就是首个元素heap[0],并返回该值

基本操作就以上这些了,如果heap已经是一个堆结构,那么任意时候heap[0]都是最小值。



发表评论

电子邮件地址不会被公开。 必填项已用*标注

*