質問する

The median is the middle value in an ordered integer list. If the size of the list is even, there is no middle value and the median is the mean of the two middle values.
For example, for arr = [2,3,4] , the median is 3 .
For example, for arr = [2,3] , the median is (2 + 3) / 2 = 2.5 .
Implement the MedianFinder class:MedianFinder() initializes the MedianFinder object.void addNum(int num) adds the integer num from the data stream to the data structure.double findMedian() returns the median of all elements so far. Answers within 10-5 of the actual answer will be accepted.

Example 1:

Input
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
Output
[null, null, null, 1.5, null, 2.0]

Explanation
MedianFinder medianFinder = new MedianFinder();
medianFinder.addNum(1);    // arr = [1]
medianFinder.addNum(2);    // arr = [1, 2]
medianFinder.findMedian(); // return 1.5 (i.e., (1 + 2) / 2)
medianFinder.addNum(3);    // arr[1, 2, 3]
medianFinder.findMedian(); // return 2.0

Constraints:

−105<=num<=105-10^5 <= num <= 10^5−105<=num<=105

There will be at least one element in the data structure before calling findMedian.
At most 5 * 10^4 calls will be made to addNum and findMedian.

Follow up:

If all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?
If 99% of all integer numbers from the stream are in the range [0, 100], how would you optimize your solution?

Pythonプール

from bisect import insort_left

class MedianFinder:

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

    def addNum(self, num: int) -> None:
        insort_left(self.nums, num)

    def findMedian(self) -> float:
        num_len = len(self.nums)
        return self.nums[num_len//2] if num_len%2==1 else (self.nums[num_len//2-1]+self.nums[num_len//2])/2


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

問題の説明

≪中心値｜Center Value｜oem_src≫:サイズ順のデータの中央にある値.データが偶数の場合、中間の2つのデータの平均値.
これはソートされたリストから中央値を出力する問題です.
空のリストを作成し、パラメータに変換した値をリストに追加する関数と、リストから中央値を出力する関数の2つの関数を作成する必要があります.

コードの説明

C++を使えば当然priority_queue(우선순위 큐)を使いますが、Pythonではheapqを使えばいいです.しかし使い方がわからなかったのでGoogleで検索してみるとbisectというモジュールが見つかりました.これは、ソートリストを維持しながら値を追加する簡単なモジュールです.docs.python.orgから詳細な使用方法が分かる.bisect.bisect_left(a, x, lo=0, hi=len(a))は、aという名前のリストにxという値(実際には追加されていない)を追加し、ソート順を維持して追加すると、インデックスに追加される回数を返します.リストの範囲(開始インデックスと終了インデックス)を設定できます.値を追加しない場合は、ポーリングを使用してリスト全体を比較します.leftを選択したのは、リストaにxがすでに存在する場合、存在する値の左側に追加され、インデックスが返されるためです.たとえば

from bisect import bisect_left, bisect_right
li = [1, 3, 7, 11]
print(bisect_left(li, 5))
print(bisect_right(li, 8))

# 결과
# 1
# 3

print(bisect_left(li, 11))
print(bisect_right(li, 11))
print(li)

# 결과
# 3
# 4
# [1, 3, 7, 11]

リストに値を直接追加するのではなく、どのインデックスに入るかを示します.では、どのようにして値を追加しますか?bisect.insort_left, bisect.insort_rightを利用すればいいです.bisect.bisect_left, bisect_rihgtは入力する位置を返しますが、insort_left, insort_rightは直接その位置に値を追加します.これを利用してこの問題を解決することができます.
ソートされていないリストで使用すると、必要な結果が得られない場合があります.二分ナビゲーションをベースにしたナビゲーションなので、必ずソートされたリストを使用します
中間値を見つけるのは難しくなく、スキップします.