Merge K sorted link list

還是昨天的合并?K 個(gè)有序鏈表，今天去社區(qū)看了下，還有更簡(jiǎn)單的解決方案，時(shí)間復(fù)雜度和空間復(fù)雜度更好，大概的思路是用python的最小堆來實(shí)現(xiàn)，每次從堆里彈出最小元素，然后最近一次哪個(gè)鏈表出了最小元素就把下一個(gè)塞進(jìn)堆里，很高效，很簡(jiǎn)潔，元祖（tuple）的運(yùn)用是這個(gè)實(shí)現(xiàn)的點(diǎn)睛之筆，下面貼出代碼

def mergeKLists(self, lists):from heap import heappop, heapify, heapreplacedummy = node = ListNode(0)# 下面這一步很贊h = [(n.val), n] for n in lists if n]# n 轉(zhuǎn) minheapheapify(h)while(h):# 取 堆里最小的值v, n = h[0]if n.next is None:heappop(h)else:＃ 彈出最小值，并把同一鏈表的下一個(gè)最小值放進(jìn)堆中heapreplace(h, (n.next.val, n.next))node.next = nnode = node.nextreturn dummy.next 復(fù)制代碼

Conclusion

想起了大佬 Linus 的那句話

"Bad programmers worry about the code. Good programmers worry about data structures and their relationships."

轉(zhuǎn)載于:https://juejin.im/post/5c7ba8626fb9a049f23d7b11

總結(jié)

以上是生活随笔為你收集整理的Leetcode03的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。