中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/find-median-from-data-stream
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这题仍然使用大小堆完成,思路见下代码
/**
* 思路:用一个最大堆和一个最小堆来保存数据,并且两堆的大小相差不能超过1
* 加入元素时分两类情况:
* 1、两堆大小相等:
* - 该元素大于等于最大堆堆顶:直接加入最小堆
* - 该元素小于最大堆堆顶:直接加入最大堆
* 2、最大堆比最小堆大1:
* - 该元素大于等于最大堆堆顶:
* 直接加入最小堆
* - 该元素小于最大堆堆顶:
* 将最大堆堆顶元素弹入最小堆,再将其加入最大堆
* 3、最小堆比最大堆大1:
* - 该元素大于等于最小堆堆顶:
* 将最小堆堆顶元素弹入最大堆,再将其加入最小堆
* - 该元素小于最小堆堆顶:
* 直接加入最大堆
*/
class MedianFinder {
private PriorityQueue<Integer> minHeap;
private PriorityQueue<Integer> maxHeap;
/** initialize your data structure here. */
public MedianFinder() {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<>(11, new Comparator<Integer>() {
public int compare(Integer i1, Integer i2) {
return i2 - i1;
}
});
}
public void addNum(int num) {
if (minHeap.isEmpty()) {
minHeap.add(num);
}
else {
if (minHeap.size() > maxHeap.size()) {
if (num > minHeap.element()) {
int temp = minHeap.poll();
minHeap.add(num);
maxHeap.add(temp);
}
else {
maxHeap.add(num);
}
}
else if (minHeap.size() < maxHeap.size()) {
if (num > maxHeap.element()) {
minHeap.add(num);
}
else {
int temp = maxHeap.poll();
maxHeap.add(num);
minHeap.add(temp);
}
}
else {
if (num > maxHeap.element()) {
minHeap.add(num);
}
else {
maxHeap.add(num);
}
}
}
}
public double findMedian() {
if (minHeap.size() == maxHeap.size()) {
return (double)(minHeap.element() + maxHeap.element()) / 2;
}
else {
return minHeap.size() > maxHeap.size() ?
minHeap.element() : maxHeap.element();
}
}
}
原文:https://www.cnblogs.com/easternE/p/14616623.html