力扣hot100-->排序
排序
1. 56. 合并区间
中等
以数组 intervals
表示若干个区间的集合,其中单个区间为 intervals[i] = [starti, endi]
。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。
示例 1:
输入:intervals = [[1,3],[2,6],[8,10],[15,18]] 输出:[[1,6],[8,10],[15,18]] 解释:区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2:
输入:intervals = [[1,4],[4,5]] 输出:[[1,5]] 解释:区间 [1,4] 和 [4,5] 可被视为重叠区间。
提示:
1 <= intervals.length <= 104
intervals[i].length == 2
0 <= starti <= endi <= 104
class Solution {
public:
vector<vector<int>> merge(vector<vector<int>>& intervals) {
vector<vector<int>> result;
int n = intervals.size();// 按照区间起始点排序
sort(intervals.begin(), intervals.end());for(int i = 0; i < n; ++i) {
// 如果结果为空或当前区间与最后一个区间不重叠,直接添加
if (result.empty() || result.back()[1] < intervals[i][0]) {
result.push_back(intervals[i]);
} else {
// 否则合并区间,更新结束点
result.back()[1] = max(result.back()[1], intervals[i][1]);
}
}return result;
}
};
2. 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 <= 105
-104 <= nums[i] <= 104
class Solution {
public:
// quickselect 函数:使用快速选择算法查找第 k 个元素
int quickselect(vector<int> &nums, int l, int r, int k) {
if (l == r) // 递归终止条件,当左右边界相同,说明找到了目标元素
return nums[k]; // 返回找到的元素int partition = nums[l]; // 选择第一个元素作为枢纽元素
int i = l - 1, j = r + 1; // 初始化左右指针
// 分区操作,将元素分为两部分,左边部分小于枢纽,右边部分大于枢纽
while (i < j) {
do i++; while (nums[i] < partition); // 找到大于或等于枢纽的元素
do j--; while (nums[j] > partition); // 找到小于或等于枢纽的元素
if (i < j)
swap(nums[i], nums[j]); // 交换两个元素,使得左边小于枢纽,右边大于枢纽
}// 根据 k 的位置判断在哪个部分继续查找
if (k <= j) // 如果 k 在左边部分,继续在左边部分查找
return quickselect(nums, l, j, k);
else // 如果 k 在右边部分,继续在右边部分查找
return quickselect(nums, j + 1, r, k);
}// findKthLargest 函数:返回数组 nums 中第 k 大的元素
int findKthLargest(vector<int> &nums, int k) {
int n = nums.size(); // 数组的大小
return quickselect(nums, 0, n - 1, n - k); // 调用 quickselect 查找第 n-k 小的元素
}
};
解释:
-
quickselect
函数:- 这是快速选择算法的核心部分,目标是查找第
k
小的元素。其工作原理与快速排序相似,但只会递归地处理包含目标元素的部分。 - 在每次递归时,选择一个枢纽元素,并通过 分区 操作将数组分成两部分:左边部分小于枢纽元素,右边部分大于枢纽元素。
- 分区操作:通过两个指针
i
和j
,i
从左边开始,j
从右边开始,分别找到大于等于枢纽的元素和小于等于枢纽的元素,并进行交换。直到两个指针相遇,完成一次分区。 - 每次递归时,判断目标
k
是否在左部分或右部分,并根据位置选择继续递归哪个部分。
- 这是快速选择算法的核心部分,目标是查找第
-
findKthLargest
函数:- 为了查找第
k
大的元素,findKthLargest
调用quickselect
来查找第n-k
小的元素(因为在排序中,第k
大的元素是第n-k
小的元素,n
是数组的长度)。 quickselect(nums, 0, n - 1, n - k)
表示在整个数组范围内,查找第n-k
小的元素,最终得到第k
大的元素。
- 为了查找第
奇思妙想:
随便写的就对了,sort函数平均时间复杂度为 O(n log n),
力扣没判错,额,嘶~~
大家看着玩玩,这绝对不是正确解答。哈哈哈
网友解释说是判题的时候数据量没拉满,拉满的话就超时了,千万不要这样写哟,否则面试出门左拐。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end()); // 排序
int n = nums.size() - k; // 找到第 k 大的元素的位置
return nums[n]; // 返回该元素
}
};
3. 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
个高频元素的集合是唯一的
// 定义自定义比较器,用于构造小顶堆
class mycomparison {
public:
// 重载 () 运算符
// 比较两个 pair 的第二个元素(即频率),实现从小到大的排列
bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {
return lhs.second > rhs.second; // 小顶堆:频率小的优先
}
};class Solution {
public:
// 主函数:获取数组中频率最高的前 K 个元素
vector<int> topKFrequent(vector<int>& nums, int k) {
// 使用哈希表统计每个元素的出现次数
unordered_map<int, int> unMap;
for (int& num : nums) {
unMap[num]++; // 记录每个数字的频率
}// 定义优先队列(小顶堆),使用自定义比较器
priority_queue<pair<int, int>, vector<pair<int, int>>, mycomparison> pq;// 遍历哈希表,将键值对插入到小顶堆中
for (auto& [key, value] : unMap) {
pq.push({key, value}); // 插入键值对// 如果堆的大小超过 k,则移除堆顶元素
if (pq.size() > k) {
pq.pop(); // 弹出频率最低的元素
}
}// 将堆中的元素提取出来,存入结果数组
vector<int> result;
while (!pq.empty()) {
result.emplace_back(pq.top().first); // 提取元素的键
pq.pop(); // 移除堆顶
}return result; // 返回前 K 个高频元素
}
};
解释:
定义了一个优先队列(即小顶堆)。
- 堆内存储:
pair<int, int>
类型的键值对,first
是数字,second
是频率。 - 比较规则:使用自定义比较器
mycomparison
,保证堆顶是当前频率最小的元素。
- 使用哈希表统计每个数字的频率。
- 使用小顶堆(优先队列)来维护频率最高的 kkk 个数字。
- 堆的大小始终保持为 kkk。
- 当堆的大小超过 kkk 时,移除堆顶元素(频率最小)。
- 最终,堆中剩下的就是频率最高的 kkk 个数字。
相关文章:

力扣hot100-->排序
排序 1. 56. 合并区间 中等 以数组 intervals 表示若干个区间的集合,其中单个区间为 intervals[i] [starti, endi] 。请你合并所有重叠的区间,并返回 一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间 。 示例 1: 输…...

【VRChat 全身动捕】VIVE 手柄改 tracker 定位器教程,低成本光学动捕解决方案(持续更新中2024.11.26)
更新 0.0.1(2024/11/26): 1.解决了内建蓝牙无法识别、“steamVR 蓝牙不可用” 的解决方案 2.解决了 tracker 虽然建立了连接但是在 steamVR 界面上看不到的问题 3.解决了 VIVE 基站1.0 无法被蓝牙识别 && 无法被 steamVR 搜索到 &…...

【Nginx】核心概念与安装配置解释
文章目录 1. 概述2. 核心概念2.1.Http服务器2.2.反向代理2.3. 负载均衡 3. 安装与配置3.1.安装3.2.配置文件解释3.2.1.全局配置块3.2.2.HTTP 配置块3.2.3.Server 块3.2.4.Location 块3.2.5.upstream3.2.6. mine.type文件 3.3.多虚拟主机配置 4. 总结 1. 概述 Nginx是我们常用的…...

Qt界面篇:QMessageBox高级用法
1、演示效果 2、用法注意 2.1 设置图标 用于显示实际图标的pixmap取决于当前的GUI样式。也可以通过设置icon pixmap属性为图标设置自定义pixmap。 QMessageBox::Icon icon(...
【二叉树】【2.1遍历二叉树】【刷题笔记】【灵神题单】
关注二叉树的三个问题: 什么情况适合自顶向下?什么时候适合用自底向上?一般来说,DFS的递归边界是空节点,什么情况下要额外把叶子节点作为递归边界?在什么情况下,DFS需要有返回值?什…...
Mongo数据库 --- Mongo Pipeline
Mongo数据库 --- Mongo Pipeline 什么是Mongo PipelineMongo Pipeline常用的几个StageExplanation with example:MongoDB $matchMongoDB $projectMongoDB $groupMongoDB $unwindMongoDB $countMongoDB $addFields Some Query Examples在C#中使用Aggreagtion Pipeline**方法一: …...

Adobe Illustrator 2024 安装教程与下载分享
介绍一下 下载直接看文章末尾 Adobe Illustrator 是一款由Adobe Systems开发的矢量图形编辑软件。它广泛应用于创建和编辑矢量图形、插图、徽标、图标、排版和广告等领域。以下是Adobe Illustrator的一些主要特点和功能: 矢量绘图:Illustrator使用矢量…...
javax.xml.ws.soap.SOAPFaultException: ZONE_OFFSET
javax.xml.ws.soap.SOAPFaultException 表示 SOAP 调用过程中发生了错误,并且服务端返回了一个 SOAP Fault。 错误信息中提到的 ZONE_OFFSET 可能指的是时区偏移量。在日期和时间处理中,时区偏移量是指格林威治标准时间 (GMT) 的偏移量。如果服务期望特…...
常用的数据结构
队列(FIFO) 栈(LIFO) 链表 hash表 hash冲突处理 开放式寻址 线性探测 表示依次检查索引为 hash(key) + 1、hash(key) + 2 ... 的位置。i 是冲突后的探查步数。公式:hash(i) = (hash(key) + i) % TableSize二次探查 规则:冲突后探查的步长是平方递增的,例如,检查位置为 hash…...

javaweb-day01-html和css初识
html:超文本标记语言 CSS:层叠样式表 1.html实现新浪新闻页面 1.1 标题排版 效果图: 1.2 标题颜色样式 1.3 标签内颜色样式 1.4设置超链接 1.5 正文排版 1.6 页面布局–盒子 (1)盒子模型 (2)页面布局…...

C++11特性(详解)
目录 1.C11简介 2.列表初始化 3.声明 1.auto 2.decltype 3.nullptr 4.范围for循环 5.智能指针 6.STL的一些变化 7.右值引用和移动语义 1.左值引用和右值引用 2.左值引用和右值引用的比较 3.右值引用的使用场景和意义 4.右值引用引用左值及其一些更深入的使用场景分…...

基于Springboot的心灵治愈交流平台系统的设计与实现
基于Springboot的心灵治愈交流平台系统 介绍 基于Springboot的心灵治愈交流平台系统,后端框架使用Springboot和mybatis,前端框架使用Vuehrml,数据库使用mysql,使用B/S架构实现前台用户系统和后台管理员系统,和不同级别…...

初识java(2)
大家好,今天我们来讲讲java中的数据类型。 java跟我们的c语言的数据类型有一些差别,那么接下来我们就来看看。 一.字面常量,其中:199,3.14,‘a’,true都是常量将其称为字面常量。(…...

AIGC--AIGC与人机协作:新的创作模式
AIGC与人机协作:新的创作模式 引言 人工智能生成内容(AIGC)正在以惊人的速度渗透到创作的各个领域。从生成文本、音乐、到图像和视频,AIGC使得创作过程变得更加快捷和高效。然而,AIGC并非完全取代了人类的创作角色&am…...

Wonder3D本地部署到算家云搭建详细教程
Wonder3D简介 Wonder3D仅需2至3分钟即可从单视图图像中重建出高度详细的纹理网格。Wonder3D首先通过跨域扩散模型生成一致的多视图法线图与相应的彩色图像,然后利用一种新颖的法线融合方法实现快速且高质量的重建。 本文详细介绍了在算家云搭建Wonder3D的流程以及…...
【设计模式】【行为型模式(Behavioral Patterns)】之状态模式(State Pattern)
1. 设计模式原理说明 状态模式(State Pattern) 是一种行为设计模式,它允许对象在其内部状态发生变化时改变其行为。这个模式的核心思想是使用不同的类来表示不同的状态,每个状态类都封装了与该状态相关的特定行为。当对象的状态发…...

QML学习 —— 34、视频媒体播放器(附源码)
效果 说明 您可以单独使用MediaPlayer播放音频内容(如音频),也可以将其与VideoOutput结合使用以渲染视频。VideoOutput项支持未转换、拉伸和均匀缩放的视频演示。有关拉伸均匀缩放演示文稿的描述,请参见fillMode属性描述。 播放可能出错问题 出现的问题: DirectS…...

【深度学习|特征增强模块】FFN(前馈神经网络)和E_FFN(增强型前馈神经网络)是transformer特征增强的重要组成部分!
【深度学习|特征增强模块】FFN(前馈神经网络)和E_FFN(增强型前馈神经网络)是transformer特征增强的重要组成部分! 【深度学习|特征增强模块】FFN(前馈神经网络)和E_FFN(增强型前馈神…...

【Qt】控件7
1.QTextEdit的简单使用 使用简单的QTextEdit,获取到的内容显示到标签上 使用textChanged信号 在槽函数中需要获取QTextEdit的内容,对应操作是: QString curorui->textEdit->toPlainText();然后显示到标签上,对应操作是: …...

F12抓包14_修改网页图片网页保存到本地
课程大纲 1、修改网页图片(2种方式二选一) 修改网页图片,需要定位到图片标签,修改<img>标签的属性。2种方法: 1. 修改为网络图片url。缺点:url失效,图片无法显示。 2. 修改为图片base64&a…...

Spark 之 入门讲解详细版(1)
1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室(Algorithms, Machines, and People Lab)开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目,8个月后成为Apache顶级项目,速度之快足见过人之处&…...
模型参数、模型存储精度、参数与显存
模型参数量衡量单位 M:百万(Million) B:十亿(Billion) 1 B 1000 M 1B 1000M 1B1000M 参数存储精度 模型参数是固定的,但是一个参数所表示多少字节不一定,需要看这个参数以什么…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...

《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...

分布式增量爬虫实现方案
之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面,避免重复抓取,以节省资源和时间。 在分布式环境下,增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路:将增量判…...

听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA
浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求,本次涉及的主要是收费汇聚交换机的配置,浪潮网络设备在高速项目很少,通…...
【Android】Android 开发 ADB 常用指令
查看当前连接的设备 adb devices 连接设备 adb connect 设备IP 断开已连接的设备 adb disconnect 设备IP 安装应用 adb install 安装包的路径 卸载应用 adb uninstall 应用包名 查看已安装的应用包名 adb shell pm list packages 查看已安装的第三方应用包名 adb shell pm list…...

day36-多路IO复用
一、基本概念 (服务器多客户端模型) 定义:单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用:应用程序通常需要处理来自多条事件流中的事件,比如我现在用的电脑,需要同时处理键盘鼠标…...
关于uniapp展示PDF的解决方案
在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项: 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库: npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...