用两个堆来实现
- 如果是偶数个的话,大顶堆用来存放顺序数据流左边的元素,小顶堆用来存放顺序数据流右边的元素,中位数为两个堆顶的平均数。
- 如果是奇数个的话,大顶堆存放顺序数据流+中位数,小顶堆用来存放顺序数据流右边的元素,中位数为大顶堆的堆顶。
import java.util.*; public class Solution { private static PriorityQueue<Integer> maxHeap= new PriorityQueue<>((o1,o2)->(o2-o1));//左区间,用大顶堆来维护 private static PriorityQueue<Integer> minHeap= new PriorityQueue<>(); //右区间,用小顶堆来维护 private static int sum = 0;//用来记录数据流元素的个数(已经插入的个数) public static void Insert(Integer num) { if(sum %2 == 0) { maxHeap.add(num);//当两个堆里的所有元素和是偶数 } else { minHeap.add(num); } //最大堆一定有数据,最小堆不一定有 //当最大堆中最顶端元素大于最小堆的最顶端元素,则交换两个元素 if(!minHeap.isEmpty() && maxHeap.peek()>minHeap.peek()) { int temp1 = minHeap.poll(); int temp2 = maxHeap.poll(); minHeap.add(temp2); maxHeap.add(temp1); } sum++; } public static Double GetMedian() { if(sum %2 == 1) { return (double)maxHeap.peek(); }else { return (minHeap.peek() + maxHeap.peek())/2.0; } } }