剑指 Offer 41. 数据流中的中位数 + 堆 + 优先队列
2024-09-06 10:08:31
剑指 Offer 41. 数据流中的中位数
Offer_41
题目详情
题解分析
- 本题使用大根堆和小根堆来解决这个寻找中位数和插入中位数的问题。
- 其实本题最直接的方法是先对数组进行排序,然后取中位数。但是,这种方法的此方法的时间复杂度为 O(N),其中包括: 查找元素插入位置 O(logN) (二分查找)、向数组某位置插入元素 O(N)(插入位置之后的元素都需要向后移动一位)。
- 建立一个 小顶堆 A 和 大顶堆 B ,各保存列表的一半元素,且规定:
3.1 A 保存 较大 的一半,长度为 \(\frac{N}{2}\)( N 为偶数)或 \(\frac{N+1}{2}\) ( N 为奇数);
3.2 B 保存 较小 的一半,长度为 \(\frac{N}{2}\)( N 为偶数)或 \(\frac{N-1}{2}\) ( N 为奇数); - 当 m = n(即 N 为 偶数):需向 A 添加一个元素。实现方法:将新元素 num 插入至 B ,再将 B 堆顶元素插入至 A ;
当 m != n(即 N 为 奇数):需向 B 添加一个元素。实现方法:将新元素 num 插入至 A ,再将 A 堆顶元素插入至 B ; - 当 m = n ( N 为 偶数):则中位数为 (小根堆的堆顶元素 + 大根堆的堆顶元素 )/2。
当 m != n( N 为 奇数):则中位数为大根堆的堆顶元素
java代码
package com.walegarrett.offer;
/**
* @Author WaleGarrett
* @Date 2021/2/7 22:03
*/
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* 题目描述:
* 如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。
* 如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
*
*/
public class Offer_41 {
/** initialize your data structure here. */
PriorityQueue<Integer> minHeap,maxHeap;//一个小根堆和一个大根堆,分别存储更大的一半数和存储更小的一半数
public Offer_41() {
minHeap = new PriorityQueue<>();//java默认就是小根堆
maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
}
public void addNum(int num) {
//向小根堆添加一个元素,首先向小根堆添加的元素应该是大根堆中最大的一个元素
if(minHeap.size() == maxHeap.size()){
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
}else{//向大根堆添加一个元素,向大根堆中添加的元素应该是小根堆中最小的一个元素
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}
/**
* 当 m = n ( N 为 偶数):则中位数为 (小根堆的堆顶元素 + 大根堆的堆顶元素 )/2。
* 当 m != n( N 为 奇数):则中位数为大根堆的堆顶元素。
* @return
*/
public double findMedian() {
if(minHeap.size() == maxHeap.size()){
return (minHeap.peek() + maxHeap.peek()) / 2.0;
}else return minHeap.peek();
}
}
复杂度分析
最新文章
- powershell例子
- Creating a radius based VPN with support for Windows clients
- 161215、MySQL 查看表结构简单命令
- static 静态代码块 动态代码块 单例
- P1066 2^k进制数
- RDLC报表系列(六) 多图表-折线图和柱状图
- 性能测试之LoardRunner 结果分析
- python基础教程(十)
- 根据URL获取图片
- 如何批量的在django中对url进行用户登陆限制
- eclipse卡,相关优化配置
- SPOJ QTREE2 (LCA - 倍增 在线)
- Egret P2 ( 一) 掉落的小球
- Worst Performing Queries
- 大数据系列之Flume+kafka 整合
- Linux字符设备驱动--No.3
- 经典.net面试题目(转载)
- gitflow工作流简介
- Intellij IDEA debug jar包
- hadoop1.0.4升级到hadoop2.2 具体流程步骤
热门文章
- map详细的复习
- poj3580 SuperMemo (Splay+区间内向一个方向移动)
- Educational Codeforces Round 87 (Rated for Div. 2)
- C++快读
- Educational Codeforces Round 95 (Rated for Div. 2) A. Buying Torches (数学)
- Linux系统编程【2】——编写who命令
- Kubernets二进制安装(16)之安装部署traefik(ingress)
- 在Python里,用股票案例讲描述性统计分析方法(内容来自我的书)
- Debian8.1 安装samba与windows共享文件,在系统重启后samba服务无法自动启动
- 如何在 网站页面中插入ppt/pdf 文件,使用插件,Native pdf 支持,chrome,Edge,Firefox,