いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 23 merge k sorted lists

更新日:

こんにちは

今回の学びは

・haep構造の特徴をしっておくべし

・実際に実装でできたらよりよし。理解もふかまるし。

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

一見、簡単そうだし。

単純にminだけ取って、ListNodeつくっていてもいける

問題だと思う

 

しかぁ〜し!ここはデータ構造のプロらしく

これに適したアレを使いましょ

 

そう!

heapです。

heapは2値木構造(二分木)で常に先頭は最小値となるような、構造だ。

つまりデータをポカポカ木にせづ、いれいっても

さいごにポクポクとりだせばいいってだけの

 

これで通れば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)で済む, 
ちょっとまて正確にあhheappush(logN)だからO(NlogN + N)

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.