当前位置: 首页 > 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;是用来降低…...

挑战杯推荐项目

“人工智能”创意赛 - 智能艺术创作助手&#xff1a;借助大模型技术&#xff0c;开发能根据用户输入的主题、风格等要求&#xff0c;生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用&#xff0c;帮助艺术家和创意爱好者激发创意、提高创作效率。 ​ - 个性化梦境…...

7.4.分块查找

一.分块查找的算法思想&#xff1a; 1.实例&#xff1a; 以上述图片的顺序表为例&#xff0c; 该顺序表的数据元素从整体来看是乱序的&#xff0c;但如果把这些数据元素分成一块一块的小区间&#xff0c; 第一个区间[0,1]索引上的数据元素都是小于等于10的&#xff0c; 第二…...

突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合

强化学习&#xff08;Reinforcement Learning, RL&#xff09;是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程&#xff0c;然后使用强化学习的Actor-Critic机制&#xff08;中文译作“知行互动”机制&#xff09;&#xff0c;逐步迭代求解…...

练习(含atoi的模拟实现,自定义类型等练习)

一、结构体大小的计算及位段 &#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; #pragma pack(4)st…...

Leetcode 3577. Count the Number of Computer Unlocking Permutations

Leetcode 3577. Count the Number of Computer Unlocking Permutations 1. 解题思路2. 代码实现 题目链接&#xff1a;3577. Count the Number of Computer Unlocking Permutations 1. 解题思路 这一题其实就是一个脑筋急转弯&#xff0c;要想要能够将所有的电脑解锁&#x…...

postgresql|数据库|只读用户的创建和删除(备忘)

CREATE USER read_only WITH PASSWORD 密码 -- 连接到xxx数据库 \c xxx -- 授予对xxx数据库的只读权限 GRANT CONNECT ON DATABASE xxx TO read_only; GRANT USAGE ON SCHEMA public TO read_only; GRANT SELECT ON ALL TABLES IN SCHEMA public TO read_only; GRANT EXECUTE O…...

第25节 Node.js 断言测试

Node.js的assert模块主要用于编写程序的单元测试时使用&#xff0c;通过断言可以提早发现和排查出错误。 稳定性: 5 - 锁定 这个模块可用于应用的单元测试&#xff0c;通过 require(assert) 可以使用这个模块。 assert.fail(actual, expected, message, operator) 使用参数…...

【算法训练营Day07】字符串part1

文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接&#xff1a;344. 反转字符串 双指针法&#xff0c;两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明

AI 领域的快速发展正在催生一个新时代&#xff0c;智能代理&#xff08;agents&#xff09;不再是孤立的个体&#xff0c;而是能够像一个数字团队一样协作。然而&#xff0c;当前 AI 生态系统的碎片化阻碍了这一愿景的实现&#xff0c;导致了“AI 巴别塔问题”——不同代理之间…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...