当前位置: 首页 > news >正文

力扣 295. 数据流的中位数

🔗 https://leetcode.cn/problems/find-median-from-data-stream/

题目

  • 数据流中不断有数添加进来,add 表示添加数据,find 返回数据流中的中位数

思路

  • 大根堆存储数据流中偏小的数据
  • 小根堆存储数据流中偏大的数据
  • 若当前的 num 比大根堆的 top 小,则加入到大根堆,反义加入小根堆
  • 保证大根堆和小根堆的 size 相差小于等于 1,超过时,挪动一下数据
  • 中位数则是 size 大的那个堆的 top,若相等则取 top / 2

代码

class MedianFinder {
public:MedianFinder() {size = 0;}void addNum(int num) {size++;if (maxheap.empty()) {maxheap.push(num);return;}if (num <= maxheap.top()) {maxheap.push(num);} else {minheap.push(num);}if (maxheap.size() - minheap.size() == 2) {minheap.push(maxheap.top());maxheap.pop();}if (minheap.size() - maxheap.size() == 2) {maxheap.push(minheap.top());minheap.pop();}}double findMedian() {if (maxheap.size() > minheap.size()) {return maxheap.top();}if (minheap.size() > maxheap.size()) {return minheap.top();} return ((double)maxheap.top() + minheap.top()) / 2;}std::priority_queue<int, std::vector<int>> maxheap;std::priority_queue<int, std::vector<int>, std::greater<int>> minheap;int size;};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
http://www.lryc.cn/news/530851.html

相关文章:

  • 【Linux】进程状态和优先级
  • 携程Java开发面试题及参考答案 (200道-上)
  • Docker 部署教程jenkins
  • 深入理解开放寻址法中的三种探测序列
  • 图像噪声处理技术:让图像更清晰的艺术
  • linux运行级别
  • 深入剖析Electron的原理
  • C++ 游戏开发:完整指南
  • WebForms SortedList 深度解析
  • 【hot100】刷题记录(12)-回文链表
  • 深入理解 Unix Shell 管道 Pipes:基础和高级用法 xargs tee awk sed等(中英双语)
  • [MySQL]事务的理论、属性与常见操作
  • RS485接口EMC
  • 快速上手mybatis教程
  • 本地部署DeepSeek-R1保姆级教程
  • blender 相机参数
  • 在GPIO控制器中,配置通用输入,读取IO口电平时,上拉和下拉起到什么作用
  • Maven工程核心概念GAVP详解:从命名规范到项目协作的基石
  • 如何利用DeepSeek打造医疗领域专属AI助手?从微调到部署全流程解析
  • Redis|前言
  • 眼见着折叠手机面临崩溃,三星计划增强抗摔能力挽救它
  • Leetcode面试高频题分类刷题总结
  • Vue.js `v-memo` 性能优化技巧
  • Altium Designer绘制原理图时画斜线的方法
  • 在K8S中,有哪几种控制器类型?
  • 什么是Rust?它有什么特点?为什么要学习Rust?
  • Golang 并发机制-3:通道(channels)机制详解
  • kamailio的kamctl的使用
  • HarmonyOS:ArkWeb进程
  • UI线程用到COM只能选单线程模型