看板Marginalman
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：
---------------------------------
class MedianFinder {
private List<Integer> dataStream;
public MedianFinder() {
dataStream = new ArrayList<>();
}
public void addNum(int num) {
int idx = Collections.binarySearch(dataStream, num);
if (idx >= 0) {
dataStream.add(idx, num);
} else {
dataStream.add(-idx - 1, num);
}
}
public double findMedian() {
int len = dataStream.size();
int mid = dataStream.get(len / 2);
if ((len & 1) == 1) {
return mid;
} else {
return ((dataStream.get(len / 2 - 1)) + mid) / 2.0;
}
}
}
---------------------------------
我不想努力了
--
https://i.imgur.com/He2OJUh.jpg
--
※ 批踢踢實業坊(ptt.cc), 來自: 49.159.111.108 (臺灣)※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1668270972.A.A6D.html
推 fxfxxxfxx: 這題應該會希望做到單次 O(logn) 11/13 00:51
→ fxfxxxfxx: 用兩個heap可以做到 addNum O(logn), findMedian O(1) 11/13 00:52
→ fxfxxxfxx: 不過我也是看別人答案才知道的 有點難想 11/13 00:53
→ Rushia: 這個HEAP用法真的滿厲害的 11/13 00:54
