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

C++的STL 堆实现获取数组堆第K大的数

编程日记 2024-04-21 19:30:00

前言

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

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

回到文章标题，获取一个数组中第K大的数，要求时间复杂度是O(n)，即一次遍历即可获取到该值。
所以普通的先排序，再获取第k个数值的方式显然不满足要求，排序最快的快速排序也需要O(log2 n)

这里就是我们前言中提到的堆数据结构堆优势了，可以构建一个最小堆，堆顶始终为堆中所有元素的最小值。当然在本次实现中，仅需要将堆堆大小限制为要求的K个即可，此时遍历完数组的元素，堆顶即为数组中第K大的值。

基本过程如下图：
在这里插入图片描述

实现如下(文末有测试代码)：

int calculte_k_maxnum(vector<int> &arr, int k) {priority_queue <int,vector<int>, greater<int>> small_heap;//有衔接队列构建最小堆if (arr.empty()) {print_erro("the array is empty\n",__LINE__);}/*按照步骤入堆*/for(int i =0;i < arr.size(); ++i) {if (small_heap.size() < k) {small_heap.push(arr[i]);} else if (small_heap.size() == k && small_heap.top() < arr[i]) {small_heap.pop();small_heap.push(arr[i]);}}/*最终的堆顶元素即为第K大的元素*/return small_heap.top();
}

测试代码如下：

#include <iostream>
#include <queue>
#include <vector>using namespace std;void print_erro(string s,int line) {cout << s <<" " << line << endl;exit(-1);
}int calculte_k_maxnum(vector<int> &arr, int k) {priority_queue <int,vector<int>, greater<int>> small_heap;if (arr.empty()) {print_erro("the array is empty\n",__LINE__);}for(int i =0;i < arr.size(); ++i) {if (small_heap.size() < k) {small_heap.push(arr[i]);} else if (small_heap.size() == k && small_heap.top() < arr[i]) {small_heap.pop();small_heap.push(arr[i]);}}return small_heap.top();
}int main(){vector<int> arr;int k;int tmp;cout << "input the number of arr you want to get max " << endl;cin >> k;cout << "input the arr number " << endl;for (int i = 0;i < 5; ++i) {cin >> tmp;arr.push_back(tmp);}cout << "the k's max number of arr is " << calculte_k_maxnum(arr,k) << endl;return 0;
}

输出如下:

input the number of arr you want to get max 
4
input the arr number 
2 4 3 6 7
the k's max number of arr is 3input the number of arr you want to get max 
1        
input the arr number 
1 4 7 9 6
the k's max number of arr is 9

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

HTML+CSS布局技巧及兼容问题【阅读季】

在IE6和IE7中，行高值必须大于字体的2px以上才能保证字体的完整显示或当作为链接时能显示下划线。 IE6 下去掉 input等元素的边框 border: 0 none; 所有浏览器都可以了边框1px {td不重叠状态}：border-collapse: collapse;（table、td需同时…

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

php 去掉数组相同元素,php怎么去掉数组中重复的元素

php去掉数组中重复的元素的方法：可以通过内置函数array_unique()来实现。array_unique()函数可以移除数组中重复的值并返回过滤后的数组。如果数组中存在多个相同元素，则只保留第一个值。php为我们提供了专门的内置函数array_unique()来解决此问题。该函…

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

Office文件的奥秘——.NET平台下不借助Office实现Word、Powerpoint等文件的解析(完)...

原文 http://www.cnblogs.com/mayswind/archive/2013/04/01/2991271.html 【题外话】这是这个系列的最后一篇文章了，为了不让自己觉得少点什么，顺便让自己感觉完美一些，就再把OOXML说一下吧。不过说实话，OOXML真的太容易解析了&…

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

Makefile (2) gdb

gdb调试 1.用debug的方式编译 -g 2.打上断点 3.单步调试 step into 进入函数里面step over 运行整个函数step return 跳出当前函数 4.继续运行 5.打印和监控值下面是栗子: 1 #include <stdlib.h>2 #include <stdio.h>3 4 static int add(int i) //创…

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

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

前言堆数据结构使用的是优先级队列实现，创建堆的时候需要指定堆中元素的排列方式，即最大堆或者最小堆最大堆即堆顶元素为堆中最大的元素最小堆即堆顶元素为堆中最小堆元素如下为一个最大堆中位数： 一组数排序后，如果元…

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

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

前言

相关文章：