こんにちは
今回の学びは
・haep構造の特徴をしっておくべし
・実際に実装でできたらよりよし。理解もふかまるし。
問題は。。。
（時間配分は5分問題理解 10分検討 10分実装 20分振り返り の一文45分構成)
まずは入出力をしっかりおさえましょう。
一見、簡単そうだし。
単純にminだけ取って、ListNodeつくっていてもいける
問題だと思う
しかぁ〜し！ここはデータ構造のプロらしく
これに適したアレを使いましょ
そう！
heapです。
heapは２値木構造(二分木)で常に先頭は最小値となるような、構造だ。
つまりデータをポカポカ木にせづ、いれいっても
さいごにポクポクとりだせばいいってだけの
これで通ればeasy問題じゃん
とさえ思うえる。データ構造をしることと、それを活かすタイミングをしるとうことと
実際に使ってみて、というみっつの小さなハードルを
超えることができれば
hardの問題でも簡単に溶けちゃうことがあるということを
証明できそうだ
実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析）は
pseudocode（擬似コード）をかいてみますか。
。。。
実際の実装はこちら
import heapq
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
heap = []
#heapq.heapify(heap)
for listnode in lists:
curr = listnode
while curr:
heapq.heappush(heap, curr.val)
curr = curr.next
if len(heap) == 0: return None
val = heapq.heappop(heap)
root = ListNode(val)
curr = root
while len(heap) > 0:
val = heapq.heappop(heap)
curr.next = ListNode(val)
curr = curr.next
return root
実装後です。timespace analysis (時間とスペースの分析）は ◯◯
O(n)といいいたいですが、heapの操作でO(nlogn)ですね。
heap自分でも実装してみましょうか。
時間があれば
まとめ
・haep構造の特徴をしっておくべし
・実際に実装でできたらよりよし。理解もふかまるし。
以上です
補足
3週間後に同じ問題にもう一回出会った。
その時、heapというのはまず頭になくk文のnodeから一番小さいやつを常にえらんでいけばいい
しかし
heapという前の解答がちらっとめに入りそうか、
そっちのほうが速いわな
と以下のように分析
見事すんなり解けた
普通位にやると、毎回kの比較が入るのでO(N*k)となる だけどheapを使えばO(N*2)で済む, ちょっとまて正確にあｈheappush(logN)だからO(NlogN + N)
以上です