Re: [閒聊] 每日LeetCode

看板Marginalman作者pandix (麵包屌)時間3年前 (2022/11/12 10:31)推噓7(7推 0噓 5→)

留言12則, 11人參與討論串97/719 (看更多)

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, 3年前 , 1^F

11/12 10:31, 1^F

推

PogChampLUL

11/12 10:32, 3年前 , 2^F

11/12 10:32, 2^F

推

weitea554

11/12 10:33, 3年前 , 3^F

11/12 10:33, 3^F