淘宝客必须做网站吗,国际学校网站建设,旅游休闲类网站的建设,shopex网站经常出错1. 数据流中位数问题
题目 LeetCode295: 中位数是有序列表中间的数#xff0c;如果列表长度是偶数#xff0c;中位数是中间两个数的平均值#xff0c; 例如:[2,3,4]的中位数是3#xff0c; [2,3]中位数是#xff08;23#xff09;/ 2 2.5 设计一个数据结构#xff1a; …1. 数据流中位数问题
题目 LeetCode295: 中位数是有序列表中间的数如果列表长度是偶数中位数是中间两个数的平均值 例如:[2,3,4]的中位数是3 [2,3]中位数是23/ 2 2.5 设计一个数据结构 void addNum(int num) 从数据流中添加一个整数到数据结构中 double findMedian()-返回目前所有元素的中位数。 思路 用大顶堆小顶堆来求解 小顶堆存储所有元素中较大的一半堆顶存储的是其中最小的数 大顶堆存储所有元素中较小的一半堆顶存储的是其中最大的数 相当于把元素分为两半我们计算中位数只需要小顶堆和大顶堆的根节点即可。 以[1,2,3,4,5]为例砍成两半后为[1,2]和[3,4,5]我们只要能快速找到2和3即可。 下面看看使用两个堆是怎么变化的 添加1进入minHeap中中位数是1添加2比民Heap堆顶元素1大进入minHeap中同时minHeap中元素超过了所有元素的总和的一半所以要平衡一下分一个给maxHeap中位数是(12)/21.5.添加3它比minHeap堆顶的元素2大进入minHeap中位数为2。添加4比minHeap堆顶的元素2大进入minHeap同时minHeap中元素超过了所有元素的总和的一半所以要平衡一下分一个给maxHeap中位数是(23)/22.5.添加5它比minHeap堆顶的元素3大进入minHeap中位数为3。 代码
public class MediaFinder {//小顶堆存储的是比较大的元素堆顶是其中的最小值PriorityQueueInteger minHeap;//大顶堆存储的是比较大的元素堆顶是其中的最大值PriorityQueueInteger maxHeap;public MediaFinder(){this.minHeap new PriorityQueueInteger();this.maxHeap new PriorityQueueInteger((a, b) - (b - a));}public void addNum(int num){//小顶堆存储的是比较大的元素num比较大元素中最小的还大所以进入minHeapif (minHeap.isEmpty() || num minHeap.peek()){minHeap.offer(num);//如果minHeap比maxHeap多两个元素就平衡if (minHeap.size() - maxHeap.size() 1){maxHeap.offer(minHeap.poll());}}else {maxHeap.offer(num);//这样可以保证多的那个元素一定在minHeap中if (maxHeap.size() - minHeap.size() 0){minHeap.offer(maxHeap.poll());}}}public double findMedian(){if (minHeap.size() maxHeap.size()){return minHeap.peek();} else if (minHeap.size() maxHeap.size()) {return maxHeap.peek();}else {return (minHeap.peek() maxHeap.peek())/2.0;}}
}
