##中位數是有序串列中間的數，如果串列長度是偶數，中位數則是中間兩個數的平均值，
例如，
[2,3,4] 的中位數是 3
[2,3] 的中位數是 (2 + 3) / 2 = 2.5
設計一個支持以下兩種操作的資料結構：
void addNum(int num) - 從資料流中添加一個整數到資料結構中，
double findMedian() - 回傳目前所有元素的中位數，
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
進階:
如果資料流中所有整數都在 0 到 100 范圍內，你將如何優化你的演算法？
基數排序的思想，使用長度101的int陣列記錄每個值的個數，
如果資料流中 99% 的整數都在 0 到 100 范圍內，你將如何優化你的演算法？
使用長度102的陣列，
思路
采用大根堆（降序優先級佇列）和小根堆（升序優先級佇列）存放數列，資料流向 左->右[->左]，
時間復雜度O(nlgn)，空間復雜度O(n)，
代碼
class MedianFinder {
private int size;
private PriorityQueue<Integer> minheap;
private PriorityQueue<Integer> maxheap;
/** initialize your data structure here. */
public MedianFinder() {
size = 0;
minheap = new PriorityQueue<>();
maxheap = new PriorityQueue<>((x,y) -> y-x);
}
public void addNum(int num) {
size++;
maxheap.add(num);
minheap.add(maxheap.poll());
if((size & 1) == 1) {
maxheap.add(minheap.poll());
}
}
public double findMedian() {
if((size & 1) == 1) {
return maxheap.peek();
}
return (double)(maxheap.peek() + minheap.peek()) / 2;
}
}
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder obj = new MedianFinder();
* obj.addNum(num);
* double param_2 = obj.findMedian();
*/
筆記
size++放置的位置
鏈接：https://leetcode-cn.com/problems/find-median-from-data-stream
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/90055.html
標籤：其他
上一篇：反碼轉換為補碼
下一篇：小波多解析度分析框架