Re: [閒聊] 每日LeetCode已回收
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
推
11/13 00:51,
3年前
, 1F
11/13 00:51, 1F
→
11/13 00:52,
3年前
, 2F
11/13 00:52, 2F
→
11/13 00:53,
3年前
, 3F
11/13 00:53, 3F
→
11/13 00:54,
3年前
, 4F
11/13 00:54, 4F
推
11/13 03:27,
3年前
, 5F
11/13 03:27, 5F
討論串 (同標題文章)
完整討論串 (本文為第 98 之 719 篇)：