【Offer】[41] 【数据流中的中位数】
2024-09-01 08:32:00
题目描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。
思路分析
- 将插入数据存放在小顶堆和大顶堆中，我们先设定如果插入的个数为偶数个时，将此值放到右边的小顶堆中，如果为奇数时，放入到左边的大顶推中。要保证左边的大顶堆要全部小于右边的小顶堆中的值，如果此时插入个数为偶数个，那么需要插入到小顶堆中，但是此时插入的值比大顶堆中的值要小，所以就将此值放入到大顶堆中，而将大顶堆最大的值插入到小顶堆中。
- Java中的大顶堆和小顶堆可以借助优先级队列PriorityQueue，默认为小顶堆，如果要实现大顶堆，则需要反转默认排序器
测试用例
- 功能测试：从数据流中读出奇数个数字:从数据流中读出偶数个数字。
- 边界值测试：从数据流中读出0个、1个、2个数字。
Java代码
public class Offer041 {
public static void main(String[] args) {
test1();
test2();
test3();
}
int k = 11;
PriorityQueue<Integer> minQ = new PriorityQueue<Integer>(); // 小顶堆，存中位数右边的数，都大
PriorityQueue<Integer> maxQ = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
// PriorityQueue默认是小顶堆，实现大顶堆，需要反转默认排序器
return o2.compareTo(o1);
}
});
private int count =0;
public void Insert(Integer num) {
count++;
if ((count & 1) == 0) {// 插入的数量为偶数 要插入右边的最小堆中
if (!maxQ.isEmpty() && num < maxQ.peek()) {// 大顶堆不为空 插入值小于左边最大堆中的数
maxQ.offer(num); //将此值插入到大顶推中
num = maxQ.poll(); // 把大顶堆中的最大值插入到小顶堆中
}
minQ.add(num);
} else {// 奇数 插入左边最大堆
if (!minQ.isEmpty() && num > minQ.peek()) {
minQ.offer(num);
num = minQ.poll();
}
maxQ.offer(num);
}
}
public Double GetMedian() {
if (count == 0)
throw new RuntimeException("error!");
double dd;
if ((count & 1) == 0) {
dd = (minQ.peek() + maxQ.peek())/2.0; // n偶数 取大顶堆和小顶堆的堆顶值／2
} else
dd = maxQ.peek(); // n为奇数 取小顶堆的最大值。
return dd;
}
private static void test1() {
}
private static void test2() {
}
private static void test3() {
}
}
代码链接
最新文章
- RabbitMQ高可用方案总结
- C# params关键字
- Python抓取页面中超链接(URL)的三中方法比较(HTMLParser、pyquery、正则表达式) <转>
- 移动端web页面使用position:fixed问题
- C# 打印多页tif
- JQuery__Tab实践
- ISO7816协商模式和特定模式
- 前端必备PS技巧
- 基于FPGA的均值滤波算法实现
- Android开发技巧——自定义控件之使用style
- 内核mailbox
- git cannot lock ref
- [SQL]LeetCode184. 部门工资最高的员工 | Department Highest Salary
- java中有哪4种整形数据类型？它们有什么不同之处？
- centos7编译安装zabbix的错误
- shadow一键安装
- mySQL 约束 (Constraints)：一、非空约束 NOT NULL 约束
- 《剑指offer》第二十六题（树的子结构）
- Docker 更改镜像存储位置
- Python基本知识3----序列