作者pandix (麵包屌)
看板Marginalman
標題Re: [閒聊] 每日LeetCode
時間Sat Nov 12 10:31:10 2022
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
--
蛤?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.251.212.49 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668220273.A.F37.html
→ kitune: 笑死 11/12 10:31
推 PogChampLUL: 蛤? 11/12 10:32
推 weitea554: 大師 :O 11/12 10:33
推 JerryChungYC: 大師 11/12 10:33
推 sustainer123: 大師 11/12 10:34
推 abx310492: 大師 11/12 10:34
→ surimodo: ???? 11/12 10:34
→ an94mod0: 大師 11/12 10:39
→ SecondRun: 笑死 11/12 10:52
→ SecondRun: 你變數名怎麼沒調整到跟題目有關係 11/12 10:53
笑死 好我改一下
※ 編輯: pandix (111.251.212.49 臺灣), 11/12/2022 10:58:45
推 fxfxxxfxx: 不准用第三方庫 禁止禁止禁止 11/12 10:58
推 NTHUlagka: 太狠了 python這題也太犯規了吧 C++就要兩個heap了 11/12 11:19