如何得到一個資料流中的中位數？如果從資料流中讀出奇數個數值，那么中位數就是所有數值排序之后位于中間的數值，如果從資料流中讀出偶數個數值，那么中位數就是所有數值排序之后中間兩個數的平均值，我們使用 Insert() 方法讀取資料流，使用 GetMedian() 方法獲取當前讀取資料的中位數
解題思路
暴力解法，按照題目意思實作代碼即可
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
ArrayList<Double> list = new ArrayList<>();
public void Insert(Integer num) {
list.add(num.doubleValue());
}
public Double GetMedian() {
Collections.sort(list);
if(list.size() % 2 != 0) {
return list.get(list.size() / 2);
} else {
return (list.get(list.size() / 2) + list.get(list.size() / 2 - 1)) / 2;
}
}
}
也可以使用 Java 提供的 PriorityQueue 集合，構建一個大頂堆和一個小頂堆，假設我們手頭上已有排好序的資料流，如果我們能將前半段放入大頂堆，后半段放入小頂堆，那么中位數就是大頂堆的根節點與小頂堆的根節點和的平均數，為了實作這個目的，主要步驟如下：
- 當插入元素數量為偶數時，將這個值插入大頂堆中，再將大頂堆中根節點（即最大值）插入到小頂堆中
- 當插入元素數量為奇數時，將這個值插入小頂堆中，再講小頂堆中根節點（即最小值）插入到大頂堆中
- 取中位數的時候，如果當前元素個數為偶數，取小頂堆和大頂堆根結點的平均值；如果當前個數為奇數，取小頂堆的根節點
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
// 小頂堆
private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
// 大頂堆
private PriorityQueue<Integer> maxHeap = new PriorityQueue<>(15, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
//記錄偶數個還是奇數個
int count = 0;
// 每次插入小頂堆的是當前大頂堆中最大的數
// 每次插入大頂堆的是當前小頂堆中最小的數
// 這樣保證小頂堆中的數永遠大于等于大頂堆中的數
// 中位數就可以方便地從兩者的根結點中獲取了
public void Insert(Integer num) {
// 個數為偶數的話，則先插入到大頂堆，然后將大頂堆中最大的數插入小頂堆中
if(count % 2 == 0){
maxHeap.offer(num);
int max = maxHeap.poll();
minHeap.offer(max);
}else{
// 個數為奇數的話，則先插入到小頂堆，然后將小頂堆中最小的數插入大頂堆中
minHeap.offer(num);
int min = minHeap.poll();
maxHeap.offer(min);
}
count++;
}
public Double GetMedian() {
// 當前為偶數個，則取小頂堆和大頂堆的堆頂元素求平均
if(count % 2 == 0){
return new Double(minHeap.peek() + maxHeap.peek())/2;
}else{
// 當前為奇數個，則直接從小頂堆中取元素即可
return new Double(minHeap.peek());
}
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/243181.html
標籤：其他