剑指Offer41,数据流中的中位数 C++

news/2025/1/24 3:04:39/

1、题目描述

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。
例如
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例 1
输入:
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]
示例 2
输入:
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]

2、VS2019上运行

使用方法一:优先队列

#include <iostream>
#include <vector>
#include <queue>using namespace std;class MedianFinder {
public:priority_queue<int, vector<int>, less<int>> queMin; // 存储较小一半数字的最大堆priority_queue<int, vector<int>, greater<int>> queMax; // 存储较大一半数字的最小堆MedianFinder() {}void addNum(int num) {if (queMin.empty() || num <= queMin.top()) { // 如果queMin为空或num小于等于queMin的堆顶元素queMin.push(num); // 将num添加到queMinif (queMax.size() + 1 < queMin.size()) { // 如果queMax的大小加1比queMin大,即queMin中的元素太多queMax.push(queMin.top()); // 将queMin的堆顶元素添加到queMaxqueMin.pop(); // 弹出queMin的堆顶元素}}else {queMax.push(num); // 将num添加到queMaxif (queMax.size() > queMin.size()) { // 如果queMax的大小比queMin大,即queMax中的元素太多queMin.push(queMax.top()); // 将queMax的堆顶元素添加到queMinqueMax.pop(); // 弹出queMax的堆顶元素}}}double findMedian() {if (queMin.size() > queMax.size()) { // 如果queMin的大小比queMax大,即元素总数为奇数return queMin.top(); // queMin的堆顶元素即为中位数}return (queMin.top() + queMax.top()) / 2.0; // 元素总数为偶数,返回queMin和queMax堆顶元素的平均值作为中位数}
};int main() {MedianFinder* obj = new MedianFinder();cout << "null" << endl;obj->addNum(1);cout << "null" << endl;obj->addNum(2);cout << "null" << endl;double median1 = obj->findMedian();cout << median1 << endl;obj->addNum(3);cout << "null" << endl;double median2 = obj->findMedian();cout << median2 << endl;return 0;
}

运行结果:
null
null
null
1.5
null
2

3、解题思路

  • 1.类成员:
    queMin 是一个最大堆,用于存储较小的一半数字。堆顶元素是堆中的最大值。
    queMax 是一个最小堆,用于存储较大的一半数字。堆顶元素是堆中的最小值。
  • 2.构造函数 MedianFinder():
    初始化 queMin 和 queMax。
  • 3.addNum(int num) 函数:
    如果 queMin 为空或者 num 小于等于 queMin 的堆顶元素,将 num 插入到 queMin 中。
    如果 queMax 中的元素数量比 queMin 多,则取出 queMin 的堆顶元素,放入 queMax 中。
    否则,将 num 插入到 queMax 中。
    如果 queMax 中的元素数量比 queMin 多,则取出 queMax 的堆顶元素,放入 queMin 中。
  • 4.findMedian() 函数:
    如果 queMin 的大小大于 queMax 的大小,则中位数在 queMin 中,直接返回 queMin 的堆顶元素。
    否则,中位数应该是 queMin 的堆顶元素和 queMax 的堆顶元素的平均值,返回两者的平均值。

4、priority_queue

  • priority_queue 是一个在逻辑上模拟队列的容器适配器,它使用堆作为底层数据结构来实现其功能。
  • 堆(heap)是一种完全二叉树结构,具有以下性质:
    1.在一个最大堆中,父节点的键值大于或等于其子节点的键值。
    2.在一个最小堆中,父节点的键值小于或等于其子节点的键值。
  • priority_queue 使用堆结构来维护元素的优先级顺序:
    1.默认情况下,priority_queue 是一个最大堆,其中优先级最高的元素位于队列的顶部。
    2.如果通过自定义比较函数,可以将 priority_queue 转换为最小堆,其中优先级最低的元素位于顶部。
  • 对于 priority_queue,可以使用 push() 将元素插入队列,pop() 删除队列中的顶部元素,top() 返回顶部元素的引用,以及其他常见的操作函数。这些操作会根据堆的性质自动维护优先级顺序。
  • 虽然 priority_queue 在逻辑上表现为一个队列,但它实际上使用堆作为底层数据结构来管理元素的优先级。这使得在插入和删除元素时具有较高的效率,并保证队列中的元素是按照优先级排列的。
  • 完全二叉树(Complete Binary Tree)是一种特殊的二叉树,其中所有层级(除了最后一层或者倒数第二层)都被完全填满,且所有节点都尽可能地靠左排列
文章来源:https://blog.csdn.net/zzzzyyyyy123456/article/details/132454695
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.ppmy.cn/news/1060275.html

相关文章

《基于 Vue 组件库 的 Webpack5 配置》2.模块规则 module.rule

配置 module.rules &#xff0c;创建模块时&#xff0c;匹配请求的规则数组&#xff1b; 可参考 webpack5 指南-管理资源&#xff1b; vue 可参考上述配置&#xff1b; js 使用 webpack babel-loader&#xff1b; css 参考 webpack 加载 CSS。注意style-loader 和 vue-style…

IO多路转接(复用)多线程 select 并发

1.select // sizeof(fd_set) 128 1024 #include <sys/time.h> #include <sys/types.h> #include <unistd.h> #include <sys/select.h> int select(int nfds, fd_set *readfds, fd_set *writefds,fd_set *exceptfds, struct timeval *timeout);- 参数…

centos下配置SFTP且限制用户访问目录

一、SFTP使用场景 ftp是大多数网站的文件传输选择工具&#xff0c;但ftp并不是非常安全&#xff0c;并且在centos上搭建的vsftpd也非常的不稳定&#xff0c;偶尔会出现权限问题&#xff0c;例如500、或是账号密码不正确等等。 而SFTP是基于默认的22端口&#xff0c;是ssh内含…

Unity 应用消息中心-MessageCenter

Ps&#xff1a;主要解决耦合问题&#xff0c;把脚本之间的联系通过不同消息类型事件形式进行贯通 1.MessageCenter主脚本 2.DelegateEvent消息类型脚本 3.MC_Default_Data具体接收类脚本 using System; using System.Collections; using System.Collections.Generic; using …

MySql增量恢复

一、 使用二进制日志的时间点恢复 注意 本节和下一节中的许多示例都使用mysql客户端来处理mysqlbinlog生成的二进制日志输出。如果您的二进制日志包含\0&#xff08;null&#xff09;字符&#xff0c;那么mysql将无法解析该输出&#xff0c;除非您使用--binary模式选项调用它。…

C语言基础之——数组

前言&#xff1a;本篇文章&#xff0c;我们将对一维数组&#xff0c;和二维数组进行展开式的讲解&#xff0c;并进行实际应用。 目录 一.一维数组 1.一维数组的创建和初始化 &#xff08;1&#xff09;数组的创建 &#xff08;2&#xff09;数组的初始化 2.一维数组的使用…

线性代数的学习和整理8:行列式相关

目录 1 从2元一次方程组求解说起 1.1 直接用方程组消元法求解 1.2 有没有其他方法呢&#xff1f;有&#xff1a;比如2阶行列式方法 1.3 3阶行列式 2 行列式的定义 2.1 矩阵里的方阵 2.2 行列式定义&#xff1a;返回值为标量的一个函数 2.3 行列式的计算公式 2.4 克拉…

无涯教程-PHP - preg_replace()函数

preg_replace() - 语法 mixed preg_replace (mixed pattern, mixed replacement, mixed string [, int limit [, int &$count]] ); preg_replace()函数的操作与POSIX函数ereg_replace()相同&#xff0c;不同之处在于可以在模式和替换输入参数中使用正则表达式。 可选的输…