数据流中的中位数 (用堆,大根堆,小根堆 )

简介: 数据流中的中位数 (用堆,大根堆,小根堆 )

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。


import java.util.Comparator;
import java.util.PriorityQueue;
public class Solution {
    /首先定义一个 最小堆  即升序
    PriorityQueue<Integer> minHeap=new PriorityQueue();
    /接着定义一个 最大堆  即降序
    PriorityQueue<Integer> maxHeap=new PriorityQueue<Integer>(21,new Comparator<Integer>(){
        public int compare(Integer o1,Integer o2){
            return o2-o1;
        }
    });
    int count=0;
    public void Insert(Integer num) {
        if(count%2==0){     /当为偶数的时候,插入小根堆
            maxHeap.offer(num);
            int max=maxHeap.poll();
            minHeap.offer(max);
        }else{          当为奇数时候,插入大根堆
            minHeap.offer(num);
            int min=minHeap.poll();
            maxHeap.offer(min);
        }
        count++;
    }
    public Double GetMedian() {
        if(count%2==0){
            return new Double(maxHeap.peek()+minHeap.peek())/2;
        }else{
            return new Double(minHeap.peek());
        }
    }
}
目录
相关文章
|
6月前
|
算法 测试技术 C++
【数据结构】【双堆】【滑动窗口】3013. 将数组分成最小总代价的子数组 II
【数据结构】【双堆】【滑动窗口】3013. 将数组分成最小总代价的子数组 II
|
算法 C++
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
剑指offer(C++)-JZ41:数据流中的中位数(算法-排序)
|
6月前
|
设计模式 算法 Java
【数据结构和算法】子数组最大平均数 I
​ 原题链接:力扣 643 题 子数组最大平均数 I 给你一个由n个元素组成的整数数组nums和一个整数k。 请你找出平均数最大且长度为k的连续子数组,并输出该最大平均数。 任何误差小于10-5的答案都将被视为正确答案。 ​
70 3
|
11月前
|
算法 测试技术 C#
C++二分查找算法的应用:将数据流变为多个不相交区间
C++二分查找算法的应用:将数据流变为多个不相交区间
|
11月前
|
算法 测试技术 C#
C++二分查找算法:有序矩阵中的第 k 个最小数组和(二)
C++二分查找算法:有序矩阵中的第 k 个最小数组和
|
11月前
|
算法 测试技术 C++
C++二分查找算法:有序矩阵中的第 k 个最小数组和(一)
C++二分查找算法:有序矩阵中的第 k 个最小数组和
|
算法 测试技术 C#
C++算法:数据流的中位数
C++算法:数据流的中位数
|
存储 算法
算法:滑动窗口解决连续区间子数组问题
算法:滑动窗口解决连续区间子数组问题
|
存储
剑指offer 42. 数据流中的中位数
剑指offer 42. 数据流中的中位数
42 0
7-234 两个有序序列的中位数
7-234 两个有序序列的中位数
114 0