【编程】典型题目:寻找数组第K大数(四种方法对比)
【编程】典型题目:寻找数组第K大数(四种方法对比)
文章目录
- 【编程】典型题目:寻找数组第K大数(四种方法对比)
- 1. 题目
- 2. 题解
- 2.1 方法一:全局排序(粗暴)
- 2.2 方法二:局部排序(略粗暴)
- 2.3 方法三:优先队列(合理)
- 2.4 方法四:快速排序(完美)
1. 题目

2. 题解
2.1 方法一:全局排序(粗暴)
使用C++中内置函数sort进行全局排序,再取第K大值:
class Solution {
public:int findKth(vector<int> a, int n, int K) {sort(a.begin(), a.end());return a[n-K];}
};
- 复杂度:O(n log n)
2.2 方法二:局部排序(略粗暴)
使用冒泡排序的思想,每次将最大的值放在数组尾部,直到第K个:
class Solution {
public:int findKth(vector<int> a, int n, int K) {for(int i=0; i<K; ++i){for(int j=0; j<n-i-1; ++j){if(a[j]>a[j+1]){int temp = a[j];a[j] = a[j+1];a[j+1] = temp;}}}return a[n-K];}
};
- 复杂度:O(nk)
2.3 方法三:优先队列(合理)
小根堆,维护一个大小为k的小根堆:
class Solution {
public:int findKth(vector<int> a, int n, int K) {priority_queue <int, deque<int>, greater<int>> nums; //队首最小,从小到大排序for(int i=0; i<n; ++i){if(i<K){nums.push(a[i]);}else{if(a[i]>nums.top()){nums.pop();nums.push(a[i]);}}}return nums.top();}
};
- 复杂度:O(n logk)
2.4 方法四:快速排序(完美)
快排思想:通过一趟排序将待排序元素分成独立的两部分,其中一部分记录的元素均比另一部分记录的元素要小,则可分别对这两部分记录继续进行排序,直到整个序列有序为止。具体做法如下:
- 首先选取基准元素base(首元素,中间元素,最后元素,随机元素等等)。
- 以基准元素为基准,将小于基准元素的元素放在前面,大于基准元素的放在后面。
- 然后以基准元素为界限,分为两组数据。
- 两组元素重复1、2和3步骤,直至比较排序完成。
快排的最坏运行时间为O(n^2),平均运行时间为O(nlogn)。由于跳跃式交换比较,故不稳定(稳定是指:值一样的原始顺序保持不变)。
针对这道题,递归直到 base 右边有k-1个数,停止即可。
class Solution {
public:vector<int> quickSort(vector<int>&nums, int start, int end, int K){if (start >= end) return nums;int base = nums[start];int i = start;int j = end;while (i < j){while (i < j && nums[j] >= base) j--; //从右往左,寻找比base小的数swap(nums[i], nums[j]);while (i < j && nums[i] <= base) i++;swap(nums[i], nums[j]);}if(nums.size()-i<K) //如果base右边的数超过K个,则第K大数肯定在base右边,此时就不需要对base左边的进行排序quickSort(nums, start, i - 1, K);quickSort(nums, i + 1, end, K);return nums;}int findKth(vector<int> a, int n, int K) {quickSort(a, 0, n-1, K);return a[n-K];}
};
- 时间复杂度:最坏O(n log n),最好O(n)
相关文章:
【编程】典型题目:寻找数组第K大数(四种方法对比)
【编程】典型题目:寻找数组第K大数(四种方法对比) 文章目录 【编程】典型题目:寻找数组第K大数(四种方法对比)1. 题目2. 题解2.1 方法一:全局排序(粗暴)2.2 方法二&#…...
Vue3 对比 Vue2 的变化
Vue3 对比 Vue2 的变化 1.源码组织方式变化:使用 TS 重写 2.支持 compositionAPI,基于函数的 api,更灵活组织组件逻辑(Vue2 使用 options api) 3.响应式系统提升:Vue3 的响应式数据原理改成了 Proxy,可以监听动态新增删…...
harbor搭建
回到目录 Harbor 是 VMware 公司开源的企业级 Docker Registry 项目,其目标是帮助用户迅速搭建一个企业级的 Docker Registry 服务 通俗的讲,harbor是一个私人镜像存储服务器 1 下载安装 进入官网,下载一个离线安装包,harbor官网下载 这…...
机器学习05-数据准备(利用 scikit-learn基于Pima Indian数据集作数据预处理)
机器学习的数据准备是指在将数据用于机器学习算法之前,对原始数据进行预处理、清洗和转换的过程。数据准备是机器学习中非常重要的一步,它直接影响了模型的性能和预测结果的准确性 以下是机器学习数据准备的一些常见步骤: 数据收集ÿ…...
【枚举+trie+dfs】CF514 C
Problem - 514C - Codeforces 题意: 思路: 其实是trie上dfs的板题 先把字符串插入到字典树中 对于每次询问,都去字典树上dfs 注意到字符集只有3,因此如果发现有不同的字符,去枚举新的字符 Code: #in…...
【计算机视觉】BLIP:统一理解和生成的自举多模态模型
文章目录 一、导读二、背景和动机三、方法3.1 模型架构3.2 预训练目标3.3 BLIP 高效率利用噪声网络数据的方法:CapFilt 四、实验4.1 实验结果4.2 各个下游任务 BLIP 与其他 VLP 模型的对比 一、导读 BLIP 是一种多模态 Transformer 模型,主要针对以往的…...
【Ansible】Ansible自动化运维工具之playbook剧本搭建LNMP架构
LNMP 一、playbooks 分布式部署 LNMP1. 环境配置2. 安装 ansble3. 安装 nginx3.1 准备 nginx 相关文件3.2 编写 lnmp.yaml 的 nginx 部分3.3 测试 nginx4. 安装 mysql4.1 准备 mysql 相关文件4.2 编写 lnmp.yaml 的 mysql 部分4.3 测试 mysql5. 安装 php5.1 编写 lnmp.yaml 的 …...
Spring中的事务
一、为什么需要事务? 事务定义 将一组操作封装成一个执行单元(封装到一起),要么全部成功,要么全部失败。 为什么要用事务? 比如转账分为两个操作: 第一步操作: A 账户 -100 元…...
38 非法地址访问的 segment fault 的调试
前言 在前面一篇文章 coredump 的生成和使用 中, 我们看到 "测试用例2 - 非法地址访问" 产生了一个 segment fault 我们这里 就来调试一下 这个 segment fault 是怎么回事 测试用例 #include "stdio.h"int main(int argc, char** argv) {int x 2; i…...
c++中c_str()的用法详解
c_str()就是将C的string转化为C的字符串数组!!! C中没有string,所以函数c_str()就是将C的string转化为C的字符串数组,c_str()生成一个const char *指针,指向字符串的首地址。 下文通过3段简单的代码比较分析…...
谈谈关于新能源汽车的话题
新能源汽车是指使用新型能源替代传统燃油的汽车,主要包括纯电动汽车、插电式混合动力汽车和燃料电池汽车等。随着环境污染和能源安全问题的日益突出,新能源汽车已经成为全球汽车行业的发展趋势。下面我们来谈谈关于新能源汽车的话题。 首先,新…...
EventBus 开源库学习(二)
整体流程阅读 EventBus在使用的时候基本分为以下几步: 1、注册订阅者 EventBus.getDefault().register(this);2、订阅者解注册,否者会导致内存泄漏 EventBus.getDefault().unregister(this);3、在订阅者中编写注解为Subscribe的事件处理函数 Subscri…...
4_Apollo4BlueLite电源管理
1.Cortex-M4 Power Modes Apollo4BlueLite支持以下4种功耗模式: ▪ High Performance Active (not a differentiated power mode for the Cortex-M4) ▪ Active ▪ Sleep ▪ Deep Sleep (1)High Performance Mode 高性能模式不是arm定…...
Pytorch入门学习——快速搭建神经网络、优化器、梯度计算
我的代码可以在我的Github找到 GIthub地址 https://github.com/QinghongShao-sqh/Pytorch_Study 因为最近有同学问我如何Nerf入门,这里就简单给出一些我的建议: (1)基本的pytorch,机器学习,深度学习知识&a…...
举例说明typescript的Exclude、Omit、Pick
一、提前知识说明:联合类型 typescript的联合类型是一种用于表示一个值可以是多种类型中的一种的类型。我们使用竖线(|)来分隔每个类型,所以number | string | boolean是一个可以是number,string或boolean的值的类型。…...
记录一次Linux环境下遇到“段错误核心已转储”然后利用core文件解决问题的过程
参考Linux 下Coredump分析与配置 在做项目的时候,很容易遇到“段错误(核心已转储)”的问题。如果是语法错误还可以很快排查出来问题,但是碰到coredump就没办法直接找到问题,可以通过设置core文件来查找问题࿰…...
WPF中自定义Loading图
纯前端方式,通过动画实现Loading样式,如图所示 <Grid Width"35" Height"35" HorizontalAlignment"Center" VerticalAlignment"Center" Name"Loading"><Grid.Resources><DrawingBrus…...
用html+javascript打造公文一键排版系统14:为半角和全角字符相互转换功能增加英文字母、阿拉伯数字、标点符号、空格选项
一、实际工作中需要对转换选项细化内容 在昨天我们实现了最简单的半角字符和全角字符相互转换功能,就是将英文字母、阿拉伯数字、标点符号、空格全部进行转换。 在实际工作中,我们有时只想英文字母、阿拉伯数字、标点符号、空格之中的一两类进行转换&a…...
叮咚买菜财报分析:叮咚买菜第二季度财报将低于市场预期
来源:猛兽财经 作者:猛兽财经 卖方分析师对叮咚买菜第二季度财报的预测 尽管叮咚买菜(DDL)尚未明确披露第二季度财报的具体日期,但根据其以往的业绩公告,猛兽财经认为叮咚买菜很有可能会在8月的第二周发布…...
设计模式行为型——中介者模式
目录 什么是中介者模式 中介者模式的实现 中介者模式角色 中介者模式类图 中介者模式代码实现 中介者模式的特点 优点 缺点 使用场景 注意事项 实际应用 什么是中介者模式 中介者模式(Mediator Pattern)属于行为型模式,是用来降低…...
调用支付宝接口响应40004 SYSTEM_ERROR问题排查
在对接支付宝API的时候,遇到了一些问题,记录一下排查过程。 Body:{"datadigital_fincloud_generalsaas_face_certify_initialize_response":{"msg":"Business Failed","code":"40004","sub_msg…...
51c自动驾驶~合集58
我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留,CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制(CCA-Attention),…...
【第二十一章 SDIO接口(SDIO)】
第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...
CentOS下的分布式内存计算Spark环境部署
一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架,相比 MapReduce 具有以下核心优势: 内存计算:数据可常驻内存,迭代计算性能提升 10-100 倍(文档段落:3-79…...
STM32标准库-DMA直接存储器存取
文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA(Direct Memory Access)直接存储器存取 DMA可以提供外设…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
基于Docker Compose部署Java微服务项目
一. 创建根项目 根项目(父项目)主要用于依赖管理 一些需要注意的点: 打包方式需要为 pom<modules>里需要注册子模块不要引入maven的打包插件,否则打包时会出问题 <?xml version"1.0" encoding"UTF-8…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
css3笔记 (1) 自用
outline: none 用于移除元素获得焦点时默认的轮廓线 broder:0 用于移除边框 font-size:0 用于设置字体不显示 list-style: none 消除<li> 标签默认样式 margin: xx auto 版心居中 width:100% 通栏 vertical-align 作用于行内元素 / 表格单元格ÿ…...
