实时中位数
题目描述
现有一些随机生成的数字要将其依次传入，请设计一个高效算法，对于每次传入一个数字后，算出当前所有传入数字的中位数。(若传入了偶数个数字则令中位数为第n/2小的数字，n为已传入数字个数)。
给定一个int数组A，为传入的数字序列，同时给定序列大小n，请返回一个int数组，代表每次传入后的中位数。保证n小于等于1000。
测试样例：
[1,2,3,4,5,6],6
返回：[1,1,2,2,3,3]
构建一个最大堆 一个最小堆 保持 最大堆的size >= 最小堆的size 且差值不超过1，且最大堆的堆顶小于最小堆的堆顶
每次返回最大堆的堆顶
import java.util.*;
public class Middle {
public int[] getMiddle(int[] A, int n) {
// write code here
// write code here
PriorityQueue<Integer> min_heap = new PriorityQueue<Integer>();
PriorityQueue<Integer> max_heap = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
});
int [] m = new int[n];
for(int i=0; i<n; i++) {
if(max_heap.size()==0 || A[i]<max_heap.peek())
max_heap.add(A[i]);
else
min_heap.add(A[i]);
if(max_heap.size() == min_heap.size()+2) {
int a = max_heap.poll();
min_heap.add(a);
}
if(max_heap.size()+1 == min_heap.size()) {
max_heap.add(min_heap.poll());
}
m[i] = max_heap.peek();
}
return m;
}
}