题目：
有一个源源不断地吐出整数的数据流，假设你有足够的空间来保存吐出的数，请设计一个名叫MedianHolder的结构，使其能随时取得之前吐出所有数的中位数
思路：
创建两个堆，一个大根堆，一个小根堆，大根堆放较小的一半数，小根堆放较大的一半数。
步骤：
1.第一个数放大根堆
2.新出现的数cur,判断与大根堆堆顶的大小，比它小进大根堆，比它大，进小根堆。
3.使两堆平衡（借助平衡二叉树思想，左右差1），超过1，取堆顶节点扔到对面去
import java.awt.List;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.PriorityQueue;
class MinHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o1 - o2;
}
}
class MaxHeapComparator implements Comparator<Integer> {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
}
class MedianHolder {
PriorityQueue<Integer> maxHeap;
PriorityQueue<Integer> minHeap;
public MedianHolder() {
maxHeap = new PriorityQueue<Integer>(new MaxHeapComparator());
minHeap = new PriorityQueue<Integer>(new MinHeapComparator());
}
public void addNumber(Integer num) {
if (maxHeap.isEmpty() || num <= maxHeap.peek()) {
maxHeap.add(num);
} else {
minHeap.add(num);
}
modifyHeap();
}
private void modifyHeap() {
if (maxHeap.size() > minHeap.size() + 1) {
minHeap.add(maxHeap.poll());
}
if (minHeap.size() > maxHeap.size() + 1) {
maxHeap.add(minHeap.poll());
}
}
public Integer getMedian() {
if (maxHeap == null) {
return null;
}
if (maxHeap.size() == minHeap.size()) {
return (maxHeap.peek() + minHeap.peek()) >> 1;
} else if (maxHeap.size() > minHeap.size()) {
return maxHeap.peek();
} else {
return minHeap.peek();
}
}
}
public class Solution {
static ArrayList<Integer> list = new ArrayList<>();
public static Integer getMediaNumber(int num) {
list.add(num);
Collections.sort(list);
int length = list.size();
if(length<2) {
return list.get(0);
}
if(length%2==0) {
return (list.get(length>>1)+list.get((length>>1)-1))>>1;
}else {
return list.get(length>>1);
}
}
public static void main(String[] args) {
int arr[] = new int[] { 8, 4, 5, 6, 9, 7, 4, 5, 2, 1, 10 };
MedianHolder m = new MedianHolder();
for (int a : arr) {
m.addNumber(a);
System.out.print(m.getMedian() + " ");
}
System.out.println();
for (int a : arr) {
System.out.print(getMediaNumber(a) + " ");
}
}
}
原文：https://www.cnblogs.com/figsprite/p/10666647.html