題目：如何得到一個數(shù)據(jù)流中的中位數(shù)糯笙？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值撩银。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值给涕，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值。我們使用Insert()方法讀取數(shù)據(jù)流蜒蕾，使用GetMedian()方法獲取當(dāng)前讀取數(shù)據(jù)的中位數(shù)稠炬。
練習(xí)地址
https://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
https://leetcode-cn.com/problems/shu-ju-liu-zhong-de-zhong-wei-shu-lcof/
參考答案
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
private PriorityQueue<Integer> mMinQueue = new PriorityQueue<>();
private PriorityQueue<Integer> mMaxQueue = new PriorityQueue<>(11, new Comparator<Integer>() {
@Override
public int compare(Integer i1, Integer i2) {
if (i1 < i2) {
return 1;
} else if (i1 > i2) {
return -1;
} else {
return 0;
}
}
});
public void Insert(Integer num) {
if (((mMinQueue.size() + mMaxQueue.size()) & 1) == 0) {
if (!mMaxQueue.isEmpty() && num < mMaxQueue.peek()) {
mMaxQueue.add(num);
num = mMaxQueue.poll();
}
mMinQueue.add(num);
} else {
if (!mMinQueue.isEmpty() && num > mMinQueue.peek()) {
mMinQueue.add(num);
num = mMinQueue.poll();
}
mMaxQueue.add(num);
}
}
public Double GetMedian() {
int size = mMinQueue.size() + mMaxQueue.size();
if (size == 0) {
return 0.0;
}
if ((size & 1) == 1) {
return (double) mMinQueue.peek();
} else {
return (mMinQueue.peek() + mMaxQueue.peek()) / 2.0;
}
}
}
復(fù)雜度分析
- 插入的時間復(fù)雜度：O(logn)。
- 插入的空間復(fù)雜度：O(1)咪啡。
- 得到中位數(shù)的時間復(fù)雜度：O(1)首启。
- 得到中位數(shù)的空間復(fù)雜度：O(1)。
