LeetCode 热题 100 堆
215. 数组中的第K个最大元素
给定整数数组
nums
和整数k
,请返回数组中第**k**
个最大的元素。请注意,你需要找的是数组排序后的第
k
个最大的元素,而不是第k
个不同的元素。你必须设计并实现时间复杂度为
O(n)
的算法解决此问题。示例 1:
输入: [3,2,1,5,6,4], k = 2 输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6], k = 4 输出: 4
提示:
1 <= k <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
借助快速排序的思想解决topK问题,快速选择将数组划分为三块,对应三种情况进行查找,不断递归即可:
[left, l - 1] [l, r] [r + 1, right]
- 当k小于等于右区间的长度,既
k <= right - r
时,继续在右区间查找第k大的数。 - 当k小于等于右区间+中间相同字符的长度,既
k <= right - l + 1
时,第k大的数就在中间区间为key
。 - 当k大于右区间+中间相同字符的长度时,既k在左区间时,在左区间查找第k大的数减去右区间+中间相同字符的长度,既第
k - (right - l + 1)
大的数。
int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));int left = 0, right = nums.size() - 1;return topK(nums, left, right, k);
}int topK(vector<int>& nums, int left, int right, int k) {if (left == right)return nums[left];// 随机获取keyint key = nums[rand() % (right - left + 1) + left];// 数组划分为三块int i = left, l = left, r = right;while (i <= r) {if (nums[i] < key)swap(nums[l++], nums[i++]);else if (nums[i] > key)swap(nums[r--], nums[i]);elsei++;}// [left, l - 1] [l, r] [r + 1, right]if (k <= right - r)return topK(nums, r + 1, right, k);else if (k <= right - l + 1)return key;elsereturn topK(nums, left, l - 1, k - (right - l + 1));
}
快速排序的思想解决topK问题,快速选择将数组划分为三块,对应三种情况进行查找,不断递归即可:
[left, l - 1] [l, r] [r + 1, right]
- 当k小于等于右区间的长度,既
k <= right - r
时,继续在右区间查找第k大的数。 - 当k小于等于右区间+中间相同字符的长度,既
k <= right - l + 1
时,第k大的数就在中间区间为key
。 - 当k大于右区间+中间相同字符的长度时,既k在左区间时,在左区间查找第k大的数减去右区间+中间相同字符的长度,既第
k - (right - l + 1)
大的数。
int findKthLargest(vector<int>& nums, int k) {srand(time(nullptr));int left = 0, right = nums.size() - 1;return topK(nums, left, right, k);
}int topK(vector<int>& nums, int left, int right, int k) {if (left == right)return nums[left];// 随机获取keyint key = nums[rand() % (right - left + 1) + left];// 数组划分为三块int i = left, l = left, r = right;while (i <= r) {if (nums[i] < key)swap(nums[l++], nums[i++]);else if (nums[i] > key)swap(nums[r--], nums[i]);elsei++;}// [left, l - 1] [l, r] [r + 1, right]if (k <= right - r)return topK(nums, r + 1, right, k);else if (k <= right - l + 1)return key;elsereturn topK(nums, left, l - 1, k - (right - l + 1));
}
347. 前 K 个高频元素
给你一个整数数组
nums
和一个整数k
,请你返回其中出现频率前k
高的元素。你可以按 任意顺序 返回答案。示例 1:
输入: nums = [1,1,1,2,2,3], k = 2 输出: [1,2]
示例 2:
输入: nums = [1], k = 1 输出: [1]
提示:
1 <= nums.length <= 105
k
的取值范围是[1, 数组中不相同的元素的个数]
- 题目数据保证答案唯一,换句话说,数组中前
k
个高频元素的集合是唯一的**进阶:**你所设计算法的时间复杂度 必须 优于
O(n log n)
,其中n
是数组大小。
优先级队列 + 哈希
vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i : nums) {hash[i]++;}auto cmp = [](pair<int, int>& a, pair<int, int>& b) {return a.second > b.second;};// 小根堆priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> que;for (auto& [num, count] : hash) {que.emplace(num, count);if (que.size() > k) {que.pop();}}vector<int> ans;while (!que.empty()) {ans.push_back(que.top().first);que.pop();}return ans;
}
快速排序
void quickSort(vector<pair<int, int>>& v, int left, int right, int k) {if (left >= right) {return;}int key = v[rand() % (right - left + 1) + left].second;int i = left, l = left, r = right;while (i <= r) {if (v[i].second < key) {swap(v[i++], v[l++]);} else if (v[i].second > key) {swap(v[i], v[r--]);} else {i++;}}// [left, l - 1] [l, r] [r + 1, right]if (k <= right - r) {quickSort(v, r + 1, right, k);} else if (k <= right - l + 1) {return;} else {quickSort(v, left, l - 1, k - (right - l + 1));}
}vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i : nums) {hash[i]++;}vector<pair<int, int>> v;for (auto& p : hash) {v.push_back(p);}srand(time(nullptr));quickSort(v, 0, v.size() - 1, k);vector<int> ans;int i = v.size() - 1;while (k--) {ans.push_back(v[i--].first);}return ans;
}
295. 数据流的中位数
中位数是有序整数列表中的中间值。如果列表的大小是偶数,则没有中间值,中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]
的中位数是3
。- 例如
arr = [2,3]
的中位数是(2 + 3) / 2 = 2.5
。实现 MedianFinder 类:
MedianFinder()
初始化MedianFinder
对象。void addNum(int num)
将数据流中的整数num
添加到数据结构中。double findMedian()
返回到目前为止所有元素的中位数。与实际答案相差10-5
以内的答案将被接受。示例 1:
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
提示:
-10^5 <= num <= 10^5
- 在调用
findMedian
之前,数据结构中至少有一个元素- 最多
5 * 10^4
次调用addNum
和findMedian
que_min
是大根堆,用于存储数据流中较小的一半元素,堆顶元素是较小的一半元素中最大的元素。que_max
是小根堆,用于存储数据流中较大的一半元素,堆顶元素是较大的一半元素中最小的元素。
priority_queue<int, vector<int>, less<int>> que_min; // 大根堆
priority_queue<int, vector<int>, greater<int>> que_max; // 小根堆MedianFinder() {}void addNum(int num) {if (que_min.empty() || num <= que_min.top()) {que_min.push(num);if (que_min.size() > que_max.size() + 1) {que_max.push(que_min.top());que_min.pop();}} else {que_max.push(num);if (que_max.size() > que_min.size()) {que_min.push(que_max.top());que_max.pop();}}
}double findMedian() {if (que_min.size() > que_max.size())return que_min.top();return (que_min.top() + que_max.top()) / 2.0;
}
相关文章:
LeetCode 热题 100 堆
215. 数组中的第K个最大元素 给定整数数组 nums 和整数 k,请返回数组中第 **k** 个最大的元素。 请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 …...
LeetCode栈 155. 最小栈
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化堆栈对象。void push(int val) 将元素val推入堆栈。void pop() 删除堆栈顶部的元素。int top() 获取堆栈顶部的元素。int get…...
Linux系统03---文件操作时间编程
目录 文件操作 1.1 缓冲区 1.2 基于缓冲区的文件操作---高级 IO 1.3 基于非缓冲区的文件操作—低级 IO 1.3.1 文件描述符 int fd; 1.3.2 函数名:open() 1.3.3 函数名:close() 1.3.4 函数名:write() 1.3.5 函数名:read(…...
4月5日作业
需求: 1.按照图示的VLAN及IP地址需求,完成相关配置 2.要求SW 1为VLAN 2/3的主根及主网关 SW2为VLAN 20/30的主根及主网关,SW1和 SW2互为备份 3.可以使用super vlan 4.上层通过静态路由协议完成数据通信过程 5.AR1为企业出口路由器…...
新一代AI架构实践:数字大脑AI+智能调度MCP+领域执行APP的黄金金字塔体系
新一代AI架构实践:数字大脑智能调度领域执行的黄金金字塔体系 一、架构本质的三层穿透性认知 1.1 核心范式转变(CPS理论升级) 传统算法架构:数据驱动 → 特征工程 → 模型训练 → 业务应用 新一代AI架构:物理规律建…...
低代码开发:重塑软件开发的未来
在数字化转型的浪潮中,企业对软件开发的需求呈爆炸式增长。然而,传统软件开发模式面临着开发周期长、成本高、技术门槛高等诸多挑战。低代码开发平台(Low-Code Development Platform)应运而生,它通过可视化编程和拖拽式…...
小型园区网实验作业
拓扑搭建: 实验需求: 1、按照图示的VLAN及IP地址需求,完成相关配置 2、要求SW1为VLAN 2/3的主根及网关 SW2 为VLAN 20/30 的主根及主网关 SW1和SW2互为备份 3、可以使用super vlan 4、上层通过静态路由协议完成数据通信过程 5、A…...
Gateway 网关 快速开始
一、核心概念 路由(route) 路由是网关中最基础的部分,路由信息包括一个ID、一个目的URI、一组断言工厂、一组Filter组成。如果断言为真,则说明请求的 URL 和配置的路由匹配。 断言(predicates) 断言函数允许开发者去定义匹配 Http Request 中…...
C++中如何使用STL中的list定义一个双向链表,并且实现增、删、改、查操作
一、STL中的 list 是双向链表,但不是循环链表,通过指针访问结点数据,它的内存空间可以是不连续的,使用它能高效地进行各种操作。 二、代码 #include <bits/stdc.h> using namespace std;// 打印链表元素的函数 void print…...
shell脚本中捕获键盘中断信号trap
在 Shell 脚本中,可以通过 trap 命令捕获键盘中断信号(通常是 SIGINT,即 CtrlC)。以下是具体的实现方法: 1.使用 trap 捕获键盘中断信号 trap 命令用于捕获信号并执行相应的命令或函数。SIGINT(信号编号为 …...
让ChatGPT用DeepReaserch指导进行学术写作
目录 ChatGPT在学术论文写作中的作用与分阶段提示词指南 1.选题阶段(确定研究课题方向) 2.文献综述阶段(调研与综述已有研究) 3.研究设计阶段(设计研究方法与框架) 4.撰写正文阶段(撰写各部…...
Compose笔记(十四)--LazyColumn
这一节了解一下Compose中的LazyColumn,在Jetpack Compose 中,LazyColumn 是一个用于高效显示长列表或可滚动垂直布局的组件。它类似于传统 Android 开发中的 RecyclerView,但专为 Compose 的声明式 UI 框架设计,能够显著优化性能&…...
CNN-SE-Attention-ITCN多特征输入回归预测(Matlab完整源码和数据)
CNN-SE-Attention-ITCN多特征输入回归预测(Matlab完整源码和数据) 目录 CNN-SE-Attention-ITCN多特征输入回归预测(Matlab完整源码和数据)预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.一种适合光伏功率回归预测的高创…...
Spring Data JPA中的List底层:深入解析ArrayList的奥秘!!!
🌟 Spring Data JPA中的List底层:深入解析ArrayList的奥秘 💡 你是否好奇过,为什么Spring Data JPA的查询方法返回的List<T>总是默认为ArrayList?本文将通过技术原理解析、验证实验和性能优化指南,为…...
redis高并发缓存架构与性能优化
Redlock实现原理 超过半数redis节点加锁成功才算成功加锁。 Redlock存在问题 如果主节点挂掉,还没有同步到从节点,重新选举出主节点,那加锁就没有加到这个新的主节点上。 如果增加redis主节点数,那么加锁的性能更差,要…...
解锁多邻国:全方位语言学习新体验
解锁多邻国:全方位语言学习新体验 在数字化学习浪潮中,多邻国(Duolingo)凭借独特优势,成为全球超 5 亿用户的语言学习首选。这款 2012 年诞生于美国匹兹堡的应用,2019 年进入中国市场后,…...
Docker部署SeraXNG接入dify报错解决
报错: 设置授权 配置凭据后,工作区中的所有成员都可以在编排应用程序时使用此工具。 SearXNG base URL* 如何获取 PluginInvokeError: {"args":{},"error_type":"ToolProviderCredentialValidationError","message&q…...
Zookeeper的作用详解
Zookeeper作为分布式协调服务,在分布式系统中承担核心协调角色,其作用可归纳为以下核心功能模块: 一、分布式协调与同步 分布式锁管理 提供独占锁和共享锁,通过创建临时顺序节点实现锁的公平竞争。例如,客户端在/distr…...
高频面试题(含笔试高频算法整理)基本总结回顾34
干货分享,感谢您的阅读! (暂存篇---后续会删除,完整版和持续更新见高频面试题基本总结回顾(含笔试高频算法整理)) 备注:引用请标注出处,同时存在的问题请在相关博客留言…...
Dify 与 n8n 对比分析:AI 应用开发与自动化工作流工具的深度比较
Dify 与 n8n 对比分析:AI 应用开发与自动化工作流工具的深度比较 摘要 本文对比分析了 Dify 和 n8n 两款工具的核心定位、功能特点、适用场景及技术门槛。Dify 专注于 AI 应用开发,适合快速搭建智能客服、知识库检索等场景;n8n 则定位于通用…...
Systemd构建容器化微服务集群管理系统
实训背景 你是一家云计算公司的 DevOps 工程师,需为某客户设计一套基于 Docker 的微服务集群管理系统,需求如下: 容器自启管理:确保三个服务(webapp、api、redis)在系统启动时自动运行。依赖顺序控制&…...
手搓多模态-04 归一化介绍
在机器学习中,归一化是一个非常重要的工具,它能帮助我们加速训练的速度。在我们前面的SiglipVisionTransformer 中,也有用到归一化层,如下代码所示: class SiglipVisionTransformer(nn.Module): ##视觉模型的第二层&am…...
nano 编辑器的使用
nano 编辑器的使用 1. 启动 nano2. 编辑文本3. 基本操作4. 保存和退出5. 其他常用快捷键6. 高级用法 nano 是一个简单易用的文本编辑器,适合初学者使用: 1. 启动 nano 在终端中输入 nano 命令,后面可以跟上你想要编辑的文件的名称。如果文件…...
如何搞定学习人工智能所需的数学?
一、明确AI所需的数学核心领域 AI的数学需求并非泛泛而谈,而是集中在几个核心领域。以下是按优先级排序的关键知识点: 线性代数 核心概念:向量、矩阵、特征值分解、奇异值分解(SVD)。应用场景:图像处理&a…...
TCP/IP五层协议
目录 1. 五层模型结构 2. 各层核心功能与协议 (1) 应用层(Application Layer) (2) 传输层(Transport Layer) (3) 网络层(Network Layer) (4) 数据链路层(Data Link Layer) (5…...
解决Opencv:TypeError: points is not a numerical tuple
最近刚开始学习Opencv,跟着b站阿婆主敲代码的时候,又又又又,又出现了bug,下面听我娓娓道来~~ --------------------------------------------------------------------------(手动分界线) 首先描述一下当时…...
LLM-大语言模型浅谈
目录 核心定义 典型代表 核心原理 用途 优势与局限 未来发展方向 LLM(Large Language Model)大语言模型,指通过海量文本数据训练 能够理解和生成人类语言的深度学习模型。 核心定义 一种基于深度神经网络(如Transformer架…...
LeetCode第132题_分割回文串II
LeetCode 第132题:分割回文串 II 题目描述 给你一个字符串 s,请你将 s 分割成一些子串,使每个子串都是回文。 返回符合要求的 最少分割次数 。 难度 困难 题目链接 点击在LeetCode中查看题目 示例 示例 1: 输入…...
【Leetcode 每日一题】368. 最大整除子集
问题背景 给你一个由 无重复 正整数组成的集合 n u m s nums nums,请你找出并返回其中最大的整除子集 a n s w e r answer answer,子集中每一元素对 ( a n s w e r [ i ] , a n s w e r [ j ] ) (answer[i], answer[j]) (answer[i],answer[j]) 都应当…...
python三大库之---pandas(二)
python三大库之—pandas(二) 文章目录 python三大库之---pandas(二)六,函数6.1、常用的统计学函数6.2重置索引 六,函数 6.1、常用的统计学函数 函数名称描述说明count()统计某个非空值的数量sum()求和mea…...
消防车调度问题:基于Matlab的优化求解
摘要 本文聚焦消防车调度问题,介绍如何将其转化为数学模型并利用Matlab进行求解。通过建立损失矩阵,以总损失最小为目标构建线性规划模型,并针对模型求解结果可能出现的不合理情况,增加消防车到达先后次序约束条件。 关键词&…...
批量将 Markdown 转换为 Word/PDF 等其它格式
在工作当中,我们经常会接触到 Markdown 格式的文档。这是一种非常方便我们做记录,做笔记的一种格式文档。现在很多互联网编辑器都是支持 Markdown 格式的,编辑起文章来更加的方便简介。有时候,我们会碰到需要将 Markdown 格式的文…...
C语言学习笔记-9
九、结构体 构造类型: 不是基本类型的数据结构也不是指针类型, 它是若干个相同或不同类型的数据构成的集合 结构体类型: 结构体是一种构造类型的数据结构,是一种或多种基本类型或构造类型的数据的集合。 1.结构体类型定义 定…...
LLM 部署(1)——LLM 部署框架对比
1 Ollama 一个专注于简化大型语言模型(LLM)在本地部署和运行的开源框架。 简化部署:Ollama使用Docker容器技术来简化LLM的部署过程 捆绑模型组件:Ollama将模型权重、配置和数据捆绑到一个包中,称为Modelfile…...
Qt坐标体系,控件坐标的设置
Qt窗口坐标体系---平面直角坐标系(笛卡尔坐标系) 以左上角为0,0坐标原点 给Qt的某个控件,设置位置,就需要指定坐标,对应这个控件来说,坐标系原点就是相对于父控件的 如: QPushButt…...
大数据系列之:Kerberos
大数据系列之:Kerberos 基本概念工作流程安全特性应用场景总结加密原理Kerberos认证流程更改您的密码授予账户访问权限票证管理Kerberos 票据属性使用 kinit 获取票据使用 klist 查看票据使用 kdestroy 销毁票据.k5identity 文件描述 Kerberos 是一种网络认证协议&a…...
【力扣hot100题】(059)单词搜索
这道题给我最大的启示就是不要什么时候都用哈希表,偶尔也要用用数组…… 是这样,一开始还沾沾自喜的以为知道了哈希表的自己一定可以比以前傻傻用数组的我要节省空间,结果发现哈希表不能存储pair用编号存储会时间超限用数组只需要7*7的空间。…...
Java全栈面试宝典:锁机制与Spring生命周期深度解析
目录 一、synchronized锁状态机全解析 🔥 问题5:synchronized四态转换与性能对比 锁状态转换流程图 锁特性对比表 CAS操作示例 二、ReentrantLock与synchronized深度对比 🔥 问题6:两大锁机制对比 核心差异矩阵 生产级Re…...
15分钟完成Odoo18.0安装与基本配置
序言:时间是我们最宝贵的财富,珍惜手上的每个时分 Odoo18发行已半年有余,不少企业也已上至生产环境进行使用了。今天我们来看看 Odoo18的安装。 本次安装我们介绍通过阿里云服务器安装Odoo18社区版。 1.服务器准备 1.1操作系统 操作系统使用ubuntu22.04ÿ…...
pom导包成功,但是就是无法使用相关类,同时报错:Library:Maven ‘xxx‘ has broken path
开发环境:Intellij 2023 一、问题记录 在maven工程的pom文件导入如下某一依赖(JGit)。没有显示导包的错误,同时在maven仓库里面找到对应的包是正常下载到相应jar的。 但是就是无法引入相关的类。打开Project Structure,在Dependencies中发现…...
Cocos Creator 进行 Web 发布后,目录结构解析
在使用 Cocos Creator 进行 Web 发布后,生成的目录结构通常包含以下内容,下面为你详细介绍: 1. index.html 这是 Web 项目的入口 HTML 文件,它会加载所需的 JavaScript 文件和资源,从而启动游戏或应用程序。示例代码…...
Linux-磁盘管理
文章目录 1、查看磁盘和文件(夹)使用情况2、磁盘分区1)查看分区情况2)MBR分区3)GPT分区 3、磁盘分区格式化4、磁盘挂载1)挂载2)卸载挂载点3)永久挂载 1、查看磁盘和文件(…...
P1149 [NOIP 2008 提高组] 火柴棒等式(DFS)
题目描述 给你 n 根火柴棍,你可以拼出多少个形如 ABC 的等式?等式中的 A、B、C 是用火柴棍拼出的整数(若该数非零,则最高位不能是 0)。用火柴棍拼数字 0∼9 的拼法如图所示: 注意: 加号与等号…...
机器学习新范式:Kubernetes + Kubeflow,解锁模型训练与部署的高效密码
一、Kubernetes在机器学习模型训练与部署中的作用 Kubernetes作为一个强大的容器编排平台,为机器学习模型的训练与部署提供了以下核心支持: 分布式训练支持:Kubernetes能够自动化部署和管理PyTorch等机器学习框架的分布式训练任务。通过利用…...
testflight上架ipa包-只有ipa包的情况下如何修改签名信息为苹果开发者账户对应的信息-ipa苹果包如何手动改签或者第三方工具改签-优雅草卓伊凡
testflight上架ipa包-只有ipa包的情况下如何修改签名信息为苹果开发者账户对应的信息-ipa苹果包如何手动改签或者第三方工具改签-优雅草卓伊凡 直接修改苹果IPA包的签名和打包信息并不是一个推荐的常规做法,因为这可能违反苹果的开发者条款,并且可能导致…...
SpringSecurity框架入门
简介 官网 Spring Security是一个Java框架,用于保护应用程序的安全性。它提供了一套全面的安全解决方案,包括身份验证、授权、防止攻击等功能。Spring Security基于过滤器链的概念,可以轻松地集成到任何基于Spring的应用程序中。它支持多种…...
AIDD-人工智能药物设计-双扩散模型结合多目标优化策略助力3D小分子药物设计
Adv. Sci. | 双扩散模型结合多目标优化策略助力3D小分子药物设计 药物发现中,如何精准且高效地设计具有理想物理化学性质的潜在药物分子,对当前的研究水平来说仍然是一项重大挑战。近年来,基于深度学习的全新分子生成(de novo molecular generation)方法取得了显著进展,…...
Python面向对象编程 - 接口隔离原则(ISP)
1. 原则定义 接口隔离原则(Interface Segregation Principle, ISP) 是SOLID原则中的"I",核心思想是: 客户端不应该被迫依赖它们不使用的接口 即:多个特定功能的接口比一个通用接口更好 2. 核心思想 将臃肿的接口拆分为更小、更具…...
mac安装浏览器闪退处理
安装 Chrome或edge后打开浏览器出现闪退,是因为权限不够。 以下是针对edge的处理方法。 sudo chown -R $(whoami) ~/Library/Application\ Support/Microsoft\ Edge sudo chmod -R 755 ~/Library/Application\ Support/Microsoft\ Edge 原因分析: 在…...
408 计算机网络 知识点记忆(5)
前言 本文基于王道考研课程与湖科大计算机网络课程教学内容,系统梳理核心知识记忆点和框架,既为个人复习沉淀思考,亦希望能与同行者互助共进。(PS:后续将持续迭代优化细节) 往期内容 408 计算机网络 知识…...