【C++算法】45.分治_快排_数组中的第K个最大元素

news/2024/12/19 22:45:53/

文章目录

    • 题目链接:
    • 题目描述:
    • 解法
    • C++ 算法代码:


题目链接:

215. 数组中的第K个最大元素


题目描述:

539c17ce94deaf7fe67885673e0c510b


解法

这种题是典型的TOPK算法

TOPK算法有四种典型的问法:

  1. K
  2. K
  3. K
  4. K

基于TOPK算法有两种办法:堆排序算法O(nlogn),快速选择算法O(n)

算法原理:

例如第K大的元素在>key的那一段,那么<key=key的两段都不用看了

f99299dff7c9522146f91db4d4d881a5

我们分别设三个区域的元素个数为a,b,c

d3a4e5db77e43d553222ef12b94a30c3


C++ 算法代码:

class Solution 
{public:int findKthLargest(vector<int>& nums, int k) {srand(time(NULL)); // 使用当前时间作为随机数生成的种子,确保每次运行程序时随机数不同return qsort(nums, 0, nums.size() - 1, k); // 调用快速选择函数(基于快速排序的分区思想)来查找第 k 大的元素}int qsort(vector<int>& nums, int l, int r, int k) // 快速选择函数,基于快速排序的分区思想,用于查找第 k 大的元素{if(l == r) return nums[l]; // 如果子区间的起始索引等于结束索引,说明找到了目标元素// 1. 随机选择基准元素int key = getRandom(nums, l, r); // 2. 根据基准元素将数组分三块//    - 小于 key 的部分//    - 等于 key 的部分//    - 大于 key 的部分int left = l - 1, right = r + 1, i = l;while(i < right){if(nums[i] < key) swap(nums[++left], nums[i++]);else if(nums[i] == key) i++;else swap(nums[--right], nums[i]);}int c = r - right + 1, b = right - left - 1; // a计算大于 key 的元素数量,b计算等于 key 的元素数量// 3. 根据 k 的值分情况讨论://    - 如果大于 key 的元素数量 c 足够大,则递归查找右边的部分//    - 如果等于 key 的元素数量 b 足够大,则当前 key 即为目标元素//    - 否则,递归查找左边的部分,调整 k 的值if(c >= k) return qsort(nums, right, r, k); else if(b + c >= k) return key; else return qsort(nums, l, left, k - b - c); //调整 k 的值为 k - b - c}int getRandom(vector<int>& nums, int left, int right) // 随机选择一个基准元素,用于快速选择{return nums[rand() % (right - left + 1) + left]; // 生成一个随机数,并将其映射到数组的索引范围内 [left, right]}
};

http://www.ppmy.cn/news/1556492.html

相关文章

docker 拉取镜像 | 创建容器 | 容器运行

拉取镜像 拉取镜像的命令&#xff1a;docker pull name &#xff08;name换为你要拉取的镜像名&#xff09; docker pull docker.1panel.live/hispark/qiankunbp:1.0.0 docker.1panel.live/hispark/qiankunbp:1.0.0为镜像名 拉取海思的镜像&#xff1a;&#xff08;如果之前拉…

基于python对pdf文件进行加密等操作

利用python对pdf文件进行操作 读取pdf-源码 import PyPDF2 # 读取pdf格式的文件 reader PyPDF2.PdfFileReader(示例文件/aaa.pdf) print(reader)# 读取指定页面的文件 page reader.getPage(0) # 输出当前页面的文本数据 print(page.extractText())读取pdf-源码解析 这段代…

LDR6500 TYPE-C转DP双向互传方案解析

在当前的数字时代&#xff0c;投屏技术已成为连接不同设备、共享内容的常用手段。LDR6500 TYPE-C转DP双向互传方案应运而生&#xff0c;凭借其灵活性和高清视频传输能力&#xff0c;满足了现代数字生活对高效能和高清晰度的需求。 一、LDR6500概述 LDR6500是由乐得瑞科技针对…

freeswitch(开启支持视频H264通话)

亲测版本centos 7.9系统–》 freeswitch1.10.9 本人freeswitch安装路径(根据自己的路径进入) /usr/local/freeswitch/etc/freeswitch场景介绍: 内部默认是不支持的,视频通话,需要开启模块使用方法: 第一步:进入vars.xml 下面找到global_codec_prefs和outbound_codec_pr…

【C语言】打牌游戏

相信你是最棒哒&#xff01;&#xff01;&#xff01; 文章目录 题目描述 正确代码 总结 题目描述 Suneet 和 Slavic 玩一个卡牌游戏。游戏规则如下&#xff1a; 每张卡片的整数值在 1 和 10之间。每位玩家获得 2 张面朝下的卡片&#xff08;因此玩家不知道自己的卡片&#…

【功能安全】软件安全架构

目录 01 软件安全架构介绍 02 软件架构设计模板 03 软件架构设计示例 01 软件安全架构介绍

fiddler设置抓取https,还抓取不到https如何解决?

一、清楚 C:\Users\Admin\AppData\Roaming\Microsoft\Crypto\RSA 目录下所有文件&#xff08;首次安装fiddler请忽略&#xff09; 二、清除电脑上的根证书&#xff0c;WINR快捷键&#xff0c;输入&#xff1a;certmgr.msc&#xff0c; 然后回车&#xff0c;查找所有fiddler证书…

【现代服务端架构】传统服务器 对比 Serverless

在现代开发中&#xff0c;选择合适的架构是至关重要的。两种非常常见的架构模式分别是 传统服务器架构 和 Serverless。它们各有优缺点&#xff0c;适合不同的应用场景。今天&#xff0c;我就带大家一起对比这两种架构&#xff0c;看看它们的差异&#xff0c;并且帮助你选择最适…