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

こんにちは

今回の学びは

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

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

問題は。。。

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

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

直近２つの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 で終わっている条件文はバグの温床

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

以上です