当前位置：首页 > 编程日记 > 正文

C++的 STL堆实现获取中位数

编程日记 2024-04-21 17:00:00

前言

堆数据结构使用的是优先级队列实现，创建堆的时候需要指定堆中元素的排列方式，即最大堆或者最小堆
最大堆即堆顶元素为堆中最大的元素
最小堆即堆顶元素为堆中最小堆元素

如下为一个最大堆
在这里插入图片描述

中位数：
一组数排序后，如果元素个数如下
奇数个数n：(int) n/2 的数
偶数个数n: (int) n/2 和(int) n/2 +1的平均数

同样此时想要获取一组数列中的中位数，且同样使用时间复杂度为O(n)进行解决，这个时候使用堆的数据结构是最为有效的

解决办法如下：
动态维护一个最大堆与一个最小堆，最大堆存储一半数据，最小堆存储一般数据，维持最大堆的堆顶比最小堆的堆顶小。
在这里插入图片描述

在维护这两个堆的过程中核心为

最大堆的堆顶元素需要小于堆小堆的堆顶元素
两个堆元素个数相差不能超过1

保证核心的情况下需要考虑如下三种情况：
a. 最大堆的元素和最小堆的元素个数相等
此时入堆需要根据进入元素和两个堆顶元素大小比较的结果从而选择入哪个堆
b. 最大堆的元素个数大于最小堆的元素个数
此时入堆需要分两种情况：进入元素的大小小于最大堆的堆顶，进入元素大小大于最大堆的堆顶
c. 最大堆的元素个数小于最小堆的元素个数
此时入堆需要分两种情况：进入元素的大小大于最小堆的堆顶，进入元素大小小于最小堆的堆顶

实现过程如下(文末有完整测试代码)：

/*
核心：
1. 保证最大堆的堆顶小于最小堆的堆顶，这样就保证了最大堆的元素都小于最小堆的元素
2. 两个堆中堆元素个数相差不能超过1
*/
void GetMedian::push(int num) {/*初始化一个最大堆即可*/if(big_heap.empty()){big_heap.push(num);return;}/*第一种情况，两个堆的大小相等*/if(big_heap.size() == small_heap.size()) {if (num <= big_heap.top()) { //元素小于最大堆堆堆顶，则入最大堆big_heap.push(num);} else { //否push最小堆small_heap.push(num);}} else if(big_heap.size() > small_heap.size()) {//第二种情况/*此时入堆元素小于最大堆的堆顶，按照第一个核心，需要入最大堆但是为了保证两个堆大小个数相差不能超过1则需要将最大堆堆堆顶取出来放入最小堆，再将当前元素入堆*/if (num <= big_heap.top()) { small_heap.push(big_heap.top());big_heap.pop();big_heap.push(num);} else { // 否则直接入最小堆small_heap.push(num);}} else { //第三种情况处理刚好和以上步骤相反if (num >= small_heap.top()) {big_heap.push(small_heap.top());small_heap.pop();small_heap.push(num);} else {big_heap.push(num);}}
}

完整测试代码如下：

#include <iostream>
#include <queue>using namespace std;class GetMedian{private:priority_queue<int,vector<int>,greater<int>> small_heap;priority_queue<int,vector<int>,less<int>> big_heap;public:GetMedian(){};void push(int num);double getMedia(); 
};void GetMedian::push(int num) {if(big_heap.empty()){big_heap.push(num);return;}if(big_heap.size() == small_heap.size()) {if (num <= big_heap.top()) {big_heap.push(num);} else {small_heap.push(num);}} else if(big_heap.size() > small_heap.size()) {if (num <= big_heap.top()) {small_heap.push(big_heap.top());big_heap.pop();big_heap.push(num);} else {small_heap.push(num);}} else {if (num >= small_heap.top()) {big_heap.push(small_heap.top());small_heap.pop();small_heap.push(num);} else {big_heap.push(num);}}
}double GetMedian::getMedia() {double median;if (small_heap.size() == big_heap.size()) {median = ((double)small_heap.top() + (double)big_heap.top()) / 2; } else if (small_heap.size() < big_heap.size()) {median = (double)big_heap.top();} else {median = (double)small_heap.top();}return median;
}int main() {GetMedian m;int tmp;int n;cout << "input the number of element " << endl;cin >> n;cout << "add " << n << " element \n" << endl;for (int i =0;i < n; ++i) {cin >> tmp;m.push(tmp);}cout << "median is " << m.getMedia() << endl;return 0;
}

输出如下:

input the number of element 
6
add 6 element 3 4 2 1 5 6
median is 3.5input the number of element 
5
add 5 element 6 5 7 3 1
median is 5

https://www.dkcj.cn/info/5020.html

php 变更 obj,PHP: 不向后兼容的变更 - Manual

不向后兼容的变更PHP 核心中不向后兼容的变更以数组形式访问非数组尝试以数组方式访问 null，bool，int，float 或 resource(例如 $null["key"])将会抛出 notice 通知。fn 关键词fn 成为了保留关键词。需要特别注意，它不能…

编程日记2024/04/21 16:30:00

正由另一进程使用，因此该进程无法访问此文件。

相信很多人都遇到过这样的问题吧最近我的电脑似乎有点抽风了,不知道为什么控制台程序,只要使用开始执行(不调试) 必然就残留在进程中而且进程管理器看不到~~ 最恶心的是,就算重启VS也还是不能生成经过一些尝试后发现在cmd中tasklist可以看到这个进程这就好办了使用taskki…

编程日记2024/04/21 16:00:00

mysql5.6下主主复制的配置实现

两台虚拟机192.168.183.131和192.168.183.132,装完系统之后直接把所有开发包都装上下载软件包mysql-5.6.10.tar.gz，cmake-2.8.10.2.tar.gz（从5.5开始mysql使用cmake来进行编译了而不是之前的configure） mysql的编译安装 1.首先安装cmake [ro…

编程日记2024/04/21 15:30:00

RSA加密传输代码示例

RSA加密传输代码示例涉及敏感数据的传输，双方最好约定使用加密解密。那RSA非对称加密就大有作为了。服务端可以保留自己的私钥，发给客户端对应的公钥。这样就可以互相加解密了。php中rsa加解密实现： 首先要生成一对公钥私钥。前提是linux机器…

编程日记2024/04/21 15:00:00

贪心：assign cookies分糖果

贪心算法的核心： 遵循某种规律，使用最少的资源来完成目标所以在了解贪心算法的时候需要明确两点寻找共有的规律每一步的迭代使用最优的策略（消耗最少的资源） 问题如下： 已知一些孩子和一些糖果，每个孩…

编程日记2024/04/21 14:30:00

mimo系统matlab,OFDM—MIMO系统的matlab程序

【实例简介】MIMO OFDM Simulator:OFDM.m: OFDM Simulator (outer function)create_channel.m: Generates a Rayleigh fading frequency-selective channel, parametrized by the antenna configuration, the OFDM configuration, and the power-delay profile.svd_decompose_c…

编程日记2024/04/21 14:00:00

软件行业项目经理主要的职责是什么?（转）

项目经理职责：1、基本职责就是确保项目目标的实现，领导项目团队准时、优质地完成全部工作。2、与客户沟通，了解项目的整体需求。并与客户保持一定的联系，即时反馈阶段性的成果，和即时更改客户提出的合理需求。3、制…

编程日记2024/04/21 13:30:00

android interview 1

1. 请描述下Activity的生命周期。必调用的三个方法：onCreate() --> onStart() --> onResume()，用AAA表示（1）父Activity启动子Activity，子Actvity退出，父Activity调用顺序如下AAA --> onF…

编程日记2024/04/21 13:00:00

Spring Boot 的 10 个核心模块

学习 Spring Boot 必须得了解它的核心模块，和 Spring 框架一样，Spring Boot 也是一个庞大的项目，也是由许多核心子模块组成的。你所需具备的基础告诉你，Spring Boot 真是个牛逼货！Spring Boot 核心配置文件详解Sprin…

编程日记2024/04/21 12:30:00

贪心：Wiggle Subsequence 摇摆序列

一个整数序列，如果两个相邻元素的差恰好正负(负正)交替出现，则该序列被称为摇摆序列。一个小于2个元素的序列直接为摇摆序列。给一个随机序列，求这个序列满足摇摆序列定义的最长子序列的长度： 输入[1,17,5,10,13,15,10,5,16,8]&…

编程日记2024/04/21 12:00:00

php 腾讯云实时音视频,腾讯云视频 -实时音视频学习日志

1、实时音视频功能h5只支持ios2、不能主动拉人建群3、pc端的demo研究整体流程可以按照腾讯音视频上面指导的步骤走，申请账号，创建应用，购买套餐。购买好套餐后然后记录sdkappid、accountType。下载密钥。在开发辅助里面有个签名(UserSig)生成…

编程日记2024/04/21 11:30:00

juery mobile select下来菜单选项提交form问题

注意： data-native-menu"false" 虽然具有渲染作用，但是无法进行js提交。 <script type"text/javascript"> $(function() { $("#category").change(function() { loadData(); }); }); function loadData(){ documen…

编程日记2024/04/21 11:00:00

android GridView item中组件获取焦点

2019独角兽企业重金招聘Python工程师标准>>> 项目中在使用GridView控件时，里面的item有imageView、buttion等子控件。但是GridView默认焦点是让item获取焦点，所以要使子控件获取焦点的话，要在gridview的属性中设置： …

编程日记2024/04/21 10:30:00

Login failed for user 'NT AUTHORITY\SYSTEM'. 原因: 无法打开明确指定的数据库。异常处理...

公司一台SQL Server服务器一直报 "Login failed for user NT AUTHORITY\SYSTEM. 原因: 无法打开明确指定的数据库。"错误，按网上所讲的正常的处理方式都没有解决。最后是发现一个公司内部人员写的服务造成的，将服务停用即可。转载于:https://…

编程日记2024/04/21 10:00:00

n-netstat 查看网络状态命令

文章目录前言语法格式输出含义使用实例列出端口占用情况 (包括监听和未监听的)列出所有处于监听状态的 Sockets显示每个协议的统计信息在 netstat 输出中显示 PID 和进程名称在 netstat 输出中不显示主机，端口和用户名 (host, port or user)持续输出 netstat 信息显…

编程日记2024/04/21 09:30:00

php win memcached 5.4,CentOS 5.4下Memcache的安装步骤(Linux+Nginx+PHP+Memcached) 电脑维修技术网...

一、源码包准备服务器端主要是安装memcache服务器端，目前的最新版本是 memcached-v1.4.4 。下载：http://memcached.googlecode.com/files/memcached-1.4.4.tar.gz另外，Memcache用到了libevent这个库用于Socket的处理，所以还需要安…

编程日记2024/04/21 09:00:00

LomoX 桌面UI框架更新，增加资源管理

修改： 1.增加lxoption工具类，提供启动的兼容，兼容旧版的，并支持注册资源启动 （蔡东赟）兼容启动项目：main.lx //资源包默认现在用 qrc:/pack/main.html 后面评估，或者等编辑器出来mai…

编程日记2024/04/21 08:30:00

Python 数据类型：列表

一、列表介绍 1. 列表可以存储一系列的值，使用中括号来定义，每个元素之间用逗号隔开，形如 [a, b, c, d]2. 列表与元组的区别是：列表中的元素是可变的，元组中的元素是不可变的 In [1]: list1 [] # 定义一个空列…

编程日记2024/04/21 08:00:00

贪心：remove K digits移除K个数字

问题描述： 已知一个使用字符串表示的非负整数num，将num中的k个数字移除，求移除k个数字后，可以获得的最小的可能的新数字。例如：num “1432219” , k 3 在去掉3个数字后得到的很多很多可能里，如1432、43…

编程日记2024/04/21 07:30:00

oracle 分组排序 update,oracle分组排序

oracle 分组排序：这个麻烦：SELECT * FROM (SELECT deptno,ename,sal,ROW_NUMBER() OVER (PARTITION BY deptno ORDER BY sal DESC ) Top3 FROM emp)WHERE Top3 < 3开窗函数也ok：代码简单点：where 11 and status2JOIN( select p…

编程日记2024/04/21 07:00:00

QLocalServer与QLocalSocket进程通讯

在Qt中，提供了多种IPC方法，作者所用的是QLocalServer和QLocalSocket。看起来好像和Socket搭上点边，实则底层是windows的name pipe。这应该是支持双工通信的。一 QLocalServer#ifndef VXMAINWINDOW_H#define VXMAINWINDOW_H#include <QWidg…

编程日记2024/04/21 06:30:00

JDBC编程步骤

JDBC编程步骤 JDBC编程大致按如下步骤进行： （1）加载数据库驱动。通常我们使用Class类的forName静态方法来加载驱动。例如如下代码： Class.forName(driverClass) driverClass就是数据库驱动类所对应的字符串例如加载…

编程日记2024/04/21 06:00:00

（13）中值滤波和双边滤波

其实中值滤波，就是那九个数值，进行排序，选择中间的数值来代替那九个数的中间位置的值，然后再从左到右，从上到下，这样移动运算下面是均值滤波和高斯滤波的基础知识中值滤波基础知识运用中值滤波&a…

编程日记2024/04/21 05:30:00

贪心：Jump Game 跳跃游戏

一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回是true或者false判断是否能够跳跃到…

编程日记2024/04/21 05:00:00

MFC之按键消息（长按处理）

想要实现长按键的一些控制，查了查可以通过捕获键盘事件，然后处理按键时需要进行的操作。下面简单的实现左右按键界面更新数值加减。 1. 重载PreTranslateMessage(MSG* pMsg)函数，在函数中捕获键盘事件并处理响应： BOOL CEditTestD…

编程日记2024/04/21 04:30:00

服务器oracle11g卸载,卸载Oracle11g步骤详解

卸载Oracle11g步骤详解用Oracle自带的卸载程序不能从根本上卸载Oracle，从而为下次的安装留下隐患，那么怎么才能完全卸载Oracle呢？那就是直接注册表清除，步骤如下：1、开始－>设置－>控制面板…

编程日记2024/04/21 04:00:00

Fedora下配置网卡

第一次在fedora下配置静态网卡，首先去网络管理里面添加并设置网卡的IP，子网掩码和默认网关出口，然后保存即可， 也可以在 /etc/sysconfig/network-scripts/ifcfg-eth0 中直接添加这些信息，对应的为网卡的IP，…

编程日记2024/04/21 03:30:00

echarts相关设置

1.显示隐藏工具栏注释toolbox即可 /* toolbox: {show : true,feature : {dataView : {show: true, readOnly: false},magicType : {show: true, type: [line, bar]},restore : {show: true},saveAsImage : {show: true}}},*/ 2.鼠标划过数据显示对应的数据 tooltip : {trig…

编程日记2024/04/21 03:00:00

贪心：jump 游戏（获取最少跳跃的次数以及跳跃路径）

一个数组存储了非负整型数据，数组中的第i个元素a[i]，代表了可以从数组第i个位置最多向前跳跃a[i]步;已知数组各元素的情况下，求是否可以从数组的第0个位置跳跃到数组的最后一个元素的位置，返回最少跳跃的次数以及跳跃过程的路径&…

编程日记2024/04/21 02:30:00

ADO.NET事务

在发布System.Transaction命名空间之前，可以直接用ADO.NET创建事务，也可以通过组件、特性和COM运行库（位于System.EnterpriseServices命名空间中）进行事务处理。本文如题所示，介绍在这些传统事务处理方式中较为简单的“…

编程日记2024/04/21 02:00:00

前言

相关文章：