当前位置: 首页 > news >正文

【编程】典型题目:寻找数组第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大数(四种方法对比)

【编程】典型题目&#xff1a;寻找数组第K大数&#xff08;四种方法对比&#xff09; 文章目录 【编程】典型题目&#xff1a;寻找数组第K大数&#xff08;四种方法对比&#xff09;1. 题目2. 题解2.1 方法一&#xff1a;全局排序&#xff08;粗暴&#xff09;2.2 方法二&#…...

Vue3 对比 Vue2 的变化

Vue3 对比 Vue2 的变化 1.源码组织方式变化&#xff1a;使用 TS 重写 2.支持 compositionAPI&#xff0c;基于函数的 api&#xff0c;更灵活组织组件逻辑(Vue2 使用 options api) 3.响应式系统提升&#xff1a;Vue3 的响应式数据原理改成了 Proxy&#xff0c;可以监听动态新增删…...

harbor搭建

回到目录 Harbor 是 VMware 公司开源的企业级 Docker Registry 项目&#xff0c;其目标是帮助用户迅速搭建一个企业级的 Docker Registry 服务 通俗的讲&#xff0c;harbor是一个私人镜像存储服务器 1 下载安装 进入官网&#xff0c;下载一个离线安装包,harbor官网下载 这…...

机器学习05-数据准备(利用 scikit-learn基于Pima Indian数据集作数据预处理)

机器学习的数据准备是指在将数据用于机器学习算法之前&#xff0c;对原始数据进行预处理、清洗和转换的过程。数据准备是机器学习中非常重要的一步&#xff0c;它直接影响了模型的性能和预测结果的准确性 以下是机器学习数据准备的一些常见步骤&#xff1a; 数据收集&#xff…...

【枚举+trie+dfs】CF514 C

Problem - 514C - Codeforces 题意&#xff1a; 思路&#xff1a; 其实是trie上dfs的板题 先把字符串插入到字典树中 对于每次询问&#xff0c;都去字典树上dfs 注意到字符集只有3&#xff0c;因此如果发现有不同的字符&#xff0c;去枚举新的字符 Code&#xff1a; #in…...

【计算机视觉】BLIP:统一理解和生成的自举多模态模型

文章目录 一、导读二、背景和动机三、方法3.1 模型架构3.2 预训练目标3.3 BLIP 高效率利用噪声网络数据的方法&#xff1a;CapFilt 四、实验4.1 实验结果4.2 各个下游任务 BLIP 与其他 VLP 模型的对比 一、导读 BLIP 是一种多模态 Transformer 模型&#xff0c;主要针对以往的…...

【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中的事务

一、为什么需要事务&#xff1f; 事务定义 将一组操作封装成一个执行单元&#xff08;封装到一起&#xff09;&#xff0c;要么全部成功&#xff0c;要么全部失败。 为什么要用事务&#xff1f; 比如转账分为两个操作&#xff1a; 第一步操作&#xff1a; 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的字符串数组&#xff01;&#xff01;&#xff01; C中没有string&#xff0c;所以函数c_str()就是将C的string转化为C的字符串数组&#xff0c;c_str()生成一个const char *指针&#xff0c;指向字符串的首地址。 下文通过3段简单的代码比较分析…...

谈谈关于新能源汽车的话题

新能源汽车是指使用新型能源替代传统燃油的汽车&#xff0c;主要包括纯电动汽车、插电式混合动力汽车和燃料电池汽车等。随着环境污染和能源安全问题的日益突出&#xff0c;新能源汽车已经成为全球汽车行业的发展趋势。下面我们来谈谈关于新能源汽车的话题。 首先&#xff0c;新…...

EventBus 开源库学习(二)

整体流程阅读 EventBus在使用的时候基本分为以下几步&#xff1a; 1、注册订阅者 EventBus.getDefault().register(this);2、订阅者解注册&#xff0c;否者会导致内存泄漏 EventBus.getDefault().unregister(this);3、在订阅者中编写注解为Subscribe的事件处理函数 Subscri…...

4_Apollo4BlueLite电源管理

1.Cortex-M4 Power Modes Apollo4BlueLite支持以下4种功耗模式&#xff1a; ▪ High Performance Active (not a differentiated power mode for the Cortex-M4) ▪ Active ▪ Sleep ▪ Deep Sleep &#xff08;1&#xff09;High Performance Mode 高性能模式不是arm定…...

Pytorch入门学习——快速搭建神经网络、优化器、梯度计算

我的代码可以在我的Github找到 GIthub地址 https://github.com/QinghongShao-sqh/Pytorch_Study 因为最近有同学问我如何Nerf入门&#xff0c;这里就简单给出一些我的建议&#xff1a; &#xff08;1&#xff09;基本的pytorch&#xff0c;机器学习&#xff0c;深度学习知识&a…...

举例说明typescript的Exclude、Omit、Pick

一、提前知识说明&#xff1a;联合类型 typescript的联合类型是一种用于表示一个值可以是多种类型中的一种的类型。我们使用竖线&#xff08;|&#xff09;来分隔每个类型&#xff0c;所以number | string | boolean是一个可以是number&#xff0c;string或boolean的值的类型。…...

记录一次Linux环境下遇到“段错误核心已转储”然后利用core文件解决问题的过程

参考Linux 下Coredump分析与配置 在做项目的时候&#xff0c;很容易遇到“段错误&#xff08;核心已转储&#xff09;”的问题。如果是语法错误还可以很快排查出来问题&#xff0c;但是碰到coredump就没办法直接找到问题&#xff0c;可以通过设置core文件来查找问题&#xff0…...

WPF中自定义Loading图

纯前端方式&#xff0c;通过动画实现Loading样式&#xff0c;如图所示 <Grid Width"35" Height"35" HorizontalAlignment"Center" VerticalAlignment"Center" Name"Loading"><Grid.Resources><DrawingBrus…...

用html+javascript打造公文一键排版系统14:为半角和全角字符相互转换功能增加英文字母、阿拉伯数字、标点符号、空格选项

一、实际工作中需要对转换选项细化内容 在昨天我们实现了最简单的半角字符和全角字符相互转换功能&#xff0c;就是将英文字母、阿拉伯数字、标点符号、空格全部进行转换。 在实际工作中&#xff0c;我们有时只想英文字母、阿拉伯数字、标点符号、空格之中的一两类进行转换&a…...

叮咚买菜财报分析:叮咚买菜第二季度财报将低于市场预期

来源&#xff1a;猛兽财经 作者&#xff1a;猛兽财经 卖方分析师对叮咚买菜第二季度财报的预测 尽管叮咚买菜&#xff08;DDL&#xff09;尚未明确披露第二季度财报的具体日期&#xff0c;但根据其以往的业绩公告&#xff0c;猛兽财经认为叮咚买菜很有可能会在8月的第二周发布…...

设计模式行为型——中介者模式

目录 什么是中介者模式 中介者模式的实现 中介者模式角色 中介者模式类图 中介者模式代码实现 中介者模式的特点 优点 缺点 使用场景 注意事项 实际应用 什么是中介者模式 中介者模式&#xff08;Mediator Pattern&#xff09;属于行为型模式&#xff0c;是用来降低…...

【Python】 -- 趣味代码 - 小恐龙游戏

文章目录 文章目录 00 小恐龙游戏程序设计框架代码结构和功能游戏流程总结01 小恐龙游戏程序设计02 百度网盘地址00 小恐龙游戏程序设计框架 这段代码是一个基于 Pygame 的简易跑酷游戏的完整实现,玩家控制一个角色(龙)躲避障碍物(仙人掌和乌鸦)。以下是代码的详细介绍:…...

盘古信息PCB行业解决方案:以全域场景重构,激活智造新未来

一、破局&#xff1a;PCB行业的时代之问 在数字经济蓬勃发展的浪潮中&#xff0c;PCB&#xff08;印制电路板&#xff09;作为 “电子产品之母”&#xff0c;其重要性愈发凸显。随着 5G、人工智能等新兴技术的加速渗透&#xff0c;PCB行业面临着前所未有的挑战与机遇。产品迭代…...

连锁超市冷库节能解决方案:如何实现超市降本增效

在连锁超市冷库运营中&#xff0c;高能耗、设备损耗快、人工管理低效等问题长期困扰企业。御控冷库节能解决方案通过智能控制化霜、按需化霜、实时监控、故障诊断、自动预警、远程控制开关六大核心技术&#xff0c;实现年省电费15%-60%&#xff0c;且不改动原有装备、安装快捷、…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

多模态图像修复系统:基于深度学习的图片修复实现

多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...

windows系统MySQL安装文档

概览&#xff1a;本文讨论了MySQL的安装、使用过程中涉及的解压、配置、初始化、注册服务、启动、修改密码、登录、退出以及卸载等相关内容&#xff0c;为学习者提供全面的操作指导。关键要点包括&#xff1a; 解压 &#xff1a;下载完成后解压压缩包&#xff0c;得到MySQL 8.…...

十九、【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建

【用户管理与权限 - 篇一】后端基础:用户列表与角色模型的初步构建 前言准备工作第一部分:回顾 Django 内置的 `User` 模型第二部分:设计并创建 `Role` 和 `UserProfile` 模型第三部分:创建 Serializers第四部分:创建 ViewSets第五部分:注册 API 路由第六部分:后端初步测…...