Re: [閒聊] 每日LeetCode

作者: Rushia (みけねこ的鼻屎)   2022-11-13 00:36:09
295. Find Median from Data Stream
實作一個資料結構,需實現兩種操作:
1.addNum(int n)
把一個資料加入流
2.findMedian()
從資料流裡面取出一個數字,若:
* 資料有偶數個:返回大小最接近中間的兩數字,並相加除二
* 資料有奇數個:返回大小排序後剛好在正中間的數字
思路:
1.插入一個元素到List並排序他,直接排序整個List不意外吃了TLE,改用binary
search來找插入元素的位置,這樣時間複雜度從O(nlogn)變成O(n),勉勉強強AC了。
(如果不存在數字,binarySearch返回的是負數的該元素應插入位置)
2.判斷list的size來決定是要返回中間元素還是左右相加除二。
Java Code:
作者: fxfxxxfxx (愛麗絲)   2022-11-13 00:51:00
這題應該會希望做到單次 O(logn)用兩個heap可以做到 addNum O(logn), findMedian O(1)不過我也是看別人答案才知道的 有點難想
作者: Rushia (みけねこ的鼻屎)   2022-11-13 00:54:00
這個HEAP用法真的滿厲害的
作者: GTR12534 (カラス)   2022-11-13 03:27:00
Pythonista 當然是直接 SortedList 幹下去

Links booklink

Contact Us: admin [ a t ] ucptt.com