ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」

概要

海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day69 「279. Perfect Squares」

次回
ゼロから始めるLeetCode Day71 「1496. Path Crossing」

Twitterやってます。

問題

295. Find Median from Data Stream

難易度はHard。
Top 100 Liked Questionsからの抜粋です。

問題としては、クラスの実装になります。

中央値は、順序付き整数リストの中間値です。リストのサイズが偶数の場合、中間値はありません。したがって、中央値は2つの中間値の平均値となります。

例えば、
[2,3,4]
中央値は3

[2,3]
中央値は(2 + 3) / 2 = 2.5

以下の2つの操作をサポートするデータ構造体を設計します。

void addNum(int num) - データストリームからデータ構造体に整数値を追加します。
double findMedian() - これまでのすべての要素の中央値を返します。

Example:

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2

解法

平均値ではなく中央値であることを念頭において、その部分をどう実装するかがかなり重要な部分になりそうですね。

他の部分はこの問題を解こうと思った人にとってはそこまで大変ではなさそうです。

class MedianFinder:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.sorted_list = []
        self.length = 0
        

    def addNum(self, num: int) -> None:
        low,high = 0,self.length-1
        while high >= low:
            mid = (high+low)//2
            if self.sorted_list[mid] > num:
                high = mid-1
            else:
                low = mid+1
        self.sorted_list.insert(low,num)
        self.length += 1
        

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            median = self.length//2
            return (self.sorted_list[median]+self.sorted_list[median-1])/2.0
        else:
            return self.sorted_list[self.length//2]


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()
# Runtime: 296 ms, faster than 30.86% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 25.2 MB, less than 18.26% of Python3 online submissions for Find Median from Data Stream.

addNumの部分で二分探索を使い、リストの長さを保存しておくことでfindMedianの中でその長さを使ってスムーズに書くことにしました。
見返してみると基本的なことの集合問題みたいな感じですね。

それぞれの断片的な知識をしっかりと覚えていれば書けますが、そこまで速度が出ない、というジレンマに陥るタイプです。ここからどうやって改善していくか、という点についてですが、二分探索の部分が少し重くなってしまっている、というのが以下の解答例で分かります。

from heapq import *

class MedianFinder:

    def __init__(self):
        self.heaps = [], []

    def addNum(self, num):
        small, large = self.heaps
        heappush(small, -heappushpop(large, num))
        if len(large) < len(small):
            heappush(large, -heappop(small))

    def findMedian(self):
        small, large = self.heaps
        if len(large) > len(small):
            return float(large[0])
        return (large[0] - small[0]) / 2.0
# Runtime: 200 ms, faster than 82.39% of Python3 online submissions for Find Median from Data Stream.
# Memory Usage: 24.6 MB, less than 98.20% of Python3 online submissions for Find Median from Data Stream.

https://leetcode.com/problems/find-median-from-data-stream/discuss/74044/Very-Short-O(log-n)-%2B-O(1)

リストを二つ用意し、それぞれをヒープとして扱うことで軽量化していますね。

僕に先の解答からこちらのように変換できる能力があれば良かったのですが、わからなかったために今回はdiscussから引っ張ってきました。

では今回はここまで。お疲れ様でした。