C++ 数据流中的中位数
2022/1/7 9:33:41
本文主要是介绍C++ 数据流中的中位数,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
//描述 //如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流,使用GetMedian()方法获取当前读取数据的中位数。 // 数据范围:数据流中数个数满足1-1000,大小满足1-1000 // 进阶: 空间复杂度O(n), 时间复杂度O(nlogn) //插入法 vector<int> buff; void Insert(int num) { if (buff.empty()) { buff.push_back(num); } else { auto it = lower_bound(buff.begin(), buff.end(), num); buff.insert(it, num); } } double GetMedian() { double result = 0.0; int length = buff.size(); if ((length & 1) == 0) { result = (double)(buff[length / 2] + buff[length / 2 - 1]) / 2; } else { result = ((double)buff[length / 2]); } return result; } //双重优先队列法 priority_queue<int> lpq; priority_queue<int, vector<int>, greater<int>> rpq; void Insert(int num) { lpq.emplace(num); rpq.emplace(lpq.top()); lpq.pop(); if (lpq.size() < rpq.size()) { lpq.emplace(rpq.top()); rpq.pop(); } } double GetMedian() { double result = 0.0; int lsz = lpq.size(); int rsz = rpq.size(); if (lsz != rsz) { result = lpq.top(); } else { result = (double)(lpq.top() + rpq.top()) / 2.0; } return result; }
这篇关于C++ 数据流中的中位数的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-15PingCAP 黄东旭参与 CCF 秀湖会议,共探开源教育未来
- 2024-05-13PingCAP 戴涛:构建面向未来的金融核心系统
- 2024-05-09flutter3.x_macos桌面os实战
- 2024-05-09Rust中的并发性:Sync 和 Send Traits
- 2024-05-08使用Ollama和OpenWebUI在CPU上玩转Meta Llama3-8B
- 2024-05-08完工标准(DoD)与验收条件(AC)究竟有什么不同?
- 2024-05-084万 star 的 NocoDB 在 sealos 上一键起,轻松把数据库编程智能表格
- 2024-05-08Mac 版Stable Diffusion WebUI的安装
- 2024-05-08解锁CodeGeeX智能问答中3项独有的隐藏技能
- 2024-05-08RAG算法优化+新增代码仓库支持,CodeGeeX的@repo功能效果提升