質問する

Medianを検索するクラス

を作成します.

ジェネレータにより初期化、

addnumデータ構造にデータを追加

findMedianを使用すると、中央値

が返されます.

に答える

の難題ですが、そんなに難しくはないでしょうか…?

まず中位ライブラリで問題を解いて、もし性能が悪いならheapを使いましょう

statistics.median

from statistics import median

class MedianFinder:

    def __init__(self):
        self.numbers = []
        
    def addNum(self, num: int) -> None:
        self.numbers.append(num)

    def findMedian(self) -> float:
        return median(self.numbers)


# Your MedianFinder object will be instantiated and called as such:
# obj = MedianFinder()
# obj.addNum(num)
# param_2 = obj.findMedian()

タイムアウト...

sort

class MedianFinder:
    def __init__(self):
        self.numbers = []
        self.length = 0

    def addNum(self, num: int) -> None:
        self.numbers.append(num)
        self.length += 1

    def findMedian(self) -> float:
        self.numbers.sort()
        if self.length % 2 == 0:
            # even
            return sum(self.numbers[self.length // 2 - 1:self.length // 2 + 1]) / 2
        else:
            return self.numbers[self.length // 2]

heapq

from heapq import heappush, heappop

class MedianFinder:
    def __init__(self):
        self.numbers = []
        self.length = 0

    def addNum(self, num: int) -> None:
        heappush(self.numbers, num)
        self.length += 1

    def findMedian(self) -> float:
        if self.length % 2 == 0:
            # even
            count = self.length//2-1
            copied = self.numbers.copy()
            for _ in range(count):
                heappop(copied)
            return (heappop(copied)+heappop(copied)) / 2
        else:
            count = self.length//2
            copied = self.numbers.copy()
            for _ in range(count):
                heappop(copied)
            return heappop(copied)

これもタイムアウト、、、、、、、、、、、
今日はここまでにしましょう.