アルゴリズム

【アルゴリズム脳トレ】leetcode hard 295 find median from data stream

投稿日:

こんにちは

今回の学びは

・if elif で終わっている条件文はバグの温

・ヒープを2つつかって二分割、という発想

 

問題は。。。

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

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

直近2つのheap使う問題が簡単に解けたので

この問題もheapつかっておけば行けるだろうと考えていました。

しかし、

最初の実装ではLTEにぶち当たりました。

正直nsmallestのtime complexityが高かった結果かなと思います。別途詳細はこちら(pythonの仕組み)で確認したいところです

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は 

なので最初は findMedian自体もそれなりにO(nlongn * 2)くらいかかっちゃってたのかなと思います。

これはO(1)とかO(n)に持っていくのがこの問題のとうてるところ

なのでしょう

それはheapの工夫です。二つのheapを利用して

ソートした時の下位半分を一つのヒープ

もう半分の上位をもう一つのヒープに

収めるという術です。

そんなことができるのでしょうか?

実際の実装はこちら

これ、デバッグでハマりました。

いかのコードは通りません。しかもテストケースが一体、どうゆう入力なのかわかりにくいのでなおさら困惑。discussionで通る解答を比較することで

ようやく提出正解することができました。

ということで参考まで微妙に通らない実装はこちら 

 

import heapq
class MedianFinder_why_this_doesnt_passed_wakaran:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max_heap = [] # smaller values
        self.min_heap = [] # larger  values


    def addNum(self, num: int) -> None:
        n = len(self.max_heap) + len(self.min_heap)
        if n == 0:
            heapq.heappush(self.max_heap, (-num, num))
        else:
            max_heap_top = self.max_heap[0][1] if len(self.max_heap) > 0 else 0
            min_heap_top = self.min_heap[0] if len(self.min_heap) > 0 else 0
            if num <= min_heap_top:
                heapq.heappush(self.max_heap, (-num, num))
            elif num > max_heap_top:
                heapq.heappush(self.min_heap, num)
            # adjust
            if len(self.max_heap) - len(self.min_heap) == 2:
                x = heapq.heappop(self.max_heap)
                heapq.heappush(self.min_heap, x[1])
            elif len(self.min_heap) - len(self.max_heap) == 2:
                x = heapq.heappop(self.min_heap)
                heapq.heappush(self.max_heap, (-x, x))



    def findMedian(self) -> float:
        if len(self.max_heap) + len(self.min_heap) == 0: return 0.0

        if len(self.max_heap) > len(self.min_heap):
            return self.max_heap[0][1]
        elif len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        else:
            max_heap_top = self.max_heap[0][1]
            min_heap_top = self.min_heap[0]
            avg = (max_heap_top + min_heap_top) / 2
            return avg

 

実際の実装はこちら

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.max_heap = [] # smaller values
        self.min_heap = [] # larger  values


    def addNum(self, num: int) -> None:
        n = len(self.max_heap) + len(self.min_heap)
        if n == 0:
            heapq.heappush(self.max_heap, (-num, num))
        else:
            if num > self.max_heap[0][1]:
                heapq.heappush(self.min_heap, num)
            else:
                heapq.heappush(self.max_heap, (-num, num))

            # adjust
            if len(self.max_heap) - len(self.min_heap) == 2:
                x = heapq.heappop(self.max_heap)
                heapq.heappush(self.min_heap, x[1])
            elif len(self.min_heap) - len(self.max_heap) == 2:
                x = heapq.heappop(self.min_heap)
                heapq.heappush(self.max_heap, (-x, x))



    def findMedian(self) -> float:
        if len(self.max_heap) + len(self.min_heap) == 0: return 0.0

        if len(self.max_heap) > len(self.min_heap):
            return self.max_heap[0][1]
        elif len(self.min_heap) > len(self.max_heap):
            return self.min_heap[0]
        else:
            max_heap_top = self.max_heap[0][1]
            min_heap_top = self.min_heap[0]
            avg = (max_heap_top + min_heap_top) / 2
            return avg

バグになっているのは

こちらのコード、このようなifのMECEになってない、危険が含まれると

考え方がいいです。

・if elif で終わっている条件文はバグの温

この部分です。一見何気ないですが、取りこぼすパターンが思いつきます。なのであります。

気をつけましょう。

if num <= min_heap_top:
    heapq.heappush(self.max_heap, (-num, num))
elif num > max_heap_top:
    heapq.heappush(self.min_heap, num)
# adjust

 

まとめ

・if elif で終わっている条件文はバグの温

・ヒープを2つつかって二分割、という発想

 

以上です

 

-アルゴリズム

Copyright© CTOを目指す日記 , 2024 All Rights Reserved.