潍坊建设网站的公司电话,免费企业网站模板 php,青岛网站建设团队,网站要怎么创建Problem: 295. 数据流的中位数 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
由于该题目的数据是动态的我们可以维护两个堆来解决该问题 1.维护一个大顶堆#xff0c;一个小顶堆 2.每个堆中元素个数接近n/2#xff1b;如果n是偶数#xff0c;两个堆中的数据个数… Problem: 295. 数据流的中位数 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
由于该题目的数据是动态的我们可以维护两个堆来解决该问题 1.维护一个大顶堆一个小顶堆 2.每个堆中元素个数接近n/2如果n是偶数两个堆中的数据个数都是n/2;如果n是奇数则大顶堆中有n/2 1个数据小顶堆中有n/2个数据 3.大顶堆中的数据值都要小于小顶堆中的数据值 即大顶堆中的堆顶元素就是中位数
解题方法 1.创建堆按思路创建一个大顶堆和小顶堆 2.维护堆 2.1.如果新插入数据小于等于大顶堆则将其插入到大顶堆中否则插入到小顶堆 2.2.插入数据后两个堆中的数据量个数不满足思路中的要求2则我们需要从一个堆中不停的将堆顶元素移动到另一个堆 复杂度
时间复杂度: a d d N u m : O ( l o g n ) addNum:O(logn) addNum:O(logn) f i n d M e d i a n : O ( 1 ) findMedian:O(1) findMedian:O(1) 空间复杂度: O ( n ) O(n) O(n) Code
class MedianFinder {/*维护一个大顶堆和小顶堆*/private PriorityQueueInteger minQueue new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o1 - o2;}});private PriorityQueueInteger maxQueue new PriorityQueue(new ComparatorInteger() {Overridepublic int compare(Integer o1, Integer o2) {return o2 - o1;}});public MedianFinder() {}/*** 数据流插入数据** param num 待插入的数据*/public void addNum(int num) {//如果插入数据小于等于大顶堆堆顶元素大顶堆直接插入if (maxQueue.isEmpty() || num maxQueue.peek()) {maxQueue.add(num);} else {minQueue.add(num);}//大顶堆数据量不能小于小顶堆while (maxQueue.size() minQueue.size()) {Integer minQueueElement minQueue.poll();maxQueue.add(minQueueElement);}//小顶堆数据量可以比大顶堆小一个while (minQueue.size() maxQueue.size() - 1) {Integer maxQueueElement maxQueue.poll();minQueue.add(maxQueueElement);}}/*** 找出中位数** return double*/public double findMedian() {//如果大顶堆数据量大于小顶堆if (maxQueue.size() minQueue.size()) {return maxQueue.peek();} else {return (maxQueue.peek() minQueue.peek()) / 2f;}}
}/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder obj new MedianFinder();* obj.addNum(num);* double param_2 obj.findMedian();*/
