題目描述
如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，
題解
/* 大頂堆，存盤左半邊元素 */
private PriorityQueue<Integer> left = new PriorityQueue<>((o1, o2) -> o2 - o1);
/* 小頂堆，存盤右半邊元素，并且右半邊元素都大于左半邊 */
private PriorityQueue<Integer> right = new PriorityQueue<>();
/* 當前資料流讀入的元素個數 */
private int N = 0;
public void Insert(Integer val) {
/* 插入要保證兩個堆存于平衡狀態 */
if (N % 2 == 0) {
/* N 為偶數的情況下插入到右半邊，
* 因為右半邊元素都要大于左半邊，但是新插入的元素不一定比左半邊元素來的大，
* 因此需要先將元素插入左半邊，然后利用左半邊為大頂堆的特點，取出堆頂元素即為最大元素，此時插入右半邊 */
left.add(val);
right.add(left.poll());
} else {
right.add(val);
left.add(right.poll());
}
N++;
}
public Double GetMedian() {
if (N % 2 == 0)
return (left.peek() + right.peek()) / 2.0;
else
return (double) right.peek();
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/266410.html
標籤：其他