295. Find Median from Data Stream
某個叫邊板的地方有一堆人在排隊追殺龍大。
麻煩幫龍大找出排在最中間的人是誰，龍大的粉絲準備要去扁他了。
設計一個資料結構，支援插入和找中位數。
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
思路:
1.沒什麼特別的，就是sorted list
import sortedcontainers
class MedianFinder:
def __init__(self):
self.marginalman = sortedcontainers.SortedList()
def addNum(self, num: int) -> None:
self.marginalman.add(num)
def findMedian(self) -> float:
n = len(self.marginalman)
return self.marginalman[n//2] if n%2 else (self.marginalman[n//2] +
self.marginalman[n//2-1])/2