LeetCode 热题 100之 堆

1.数组中第k个最大元素

在这里插入图片描述
和Acwing 786 第k个数一模一样 排序

思路分析1:此题要求时间复杂度未为O(n)。虽然库函数sort和快速排序都能过,但是时间复杂度不满足条件。下面优化快速排序,写一个快速选择算法。我们可以引入随机化来加速这个过程,它的时间代价的期望是 O(n)。

  • 我们的目标是找到第 k 大的元素。根据索引的定义,第 k 大的元素在从小到大排序后的数组中对应的是第 n - k 小的元素(n 是数组长度)。
  • 调用 quickselect 函数,将 n - k 作为目标索引位置。
  • 辅助函数 quickselect:
    • 如果 l == r,表示区间只剩一个元素,直接返回该元素。
    • 将区间的第一个元素 nums[l] 设为基准值 partition,并初始化两个指针 i 和 j,分别从左向右和从右向左查找。
    • 使用双指针分区法:i 向右查找直到找到第一个大于或等于 partition 的元素,j 向左查找直到找到第一个小于或等于 partition 的元素。如果 i < j,交换 nums[i] 和 nums[j]。
    • 分区结束后,根据 k 的位置选择下一步要递归的区间:如果 k 在 j 的左侧,则递归左侧;否则,递归右侧。

具体实现代码(详解版):

class Solution {
public:// Quickselect函数,用于在区间 [l, r] 内找到第 k 小的元素int quickselect(vector<int> &nums, int l, int r, int k) {// 如果区间只剩一个元素,直接返回该元素if (l == r)return nums[k];// 选择区间的第一个元素作为基准值(pivot)int partition = nums[l];// 初始化左右指针,i 在 l 的前一位,j 在 r 的后一位int i = l - 1, j = r + 1;// 进行分区操作while (i < j) {// 从左到右找到第一个大于或等于基准值的元素do i++; while (nums[i] < partition);// 从右到左找到第一个小于或等于基准值的元素do j--; while (nums[j] > partition);// 如果 i 和 j 没有交叉,交换 nums[i] 和 nums[j]if (i < j)swap(nums[i], nums[j]);}// 现在 j 是分区位置的边界:所有小于基准值的元素在 j 左边,反之在右边// 根据 k 的位置选择继续搜索的区间if (k <= j) // 如果 k 位于左侧区间,则在左侧递归return quickselect(nums, l, j, k);else // 如果 k 位于右侧区间,则在右侧递归return quickselect(nums, j + 1, r, k);}// 主函数:找到数组中第 k 个最大的元素int findKthLargest(vector<int> &nums, int k) {int n = nums.size();// 第 k 大的元素在排序后是第 n - k 小的元素(索引从0开始)return quickselect(nums, 0, n - 1, n - k);}
  • 时间复杂度:
    • 平均情况下,quickselect 的时间复杂度是O(n),因为每次递归都有效缩小了查找区间。
    • 最坏情况下,时间复杂度为 O ( n 2 ) O(n^ 2 ) O(n2),可以通过随机选择基准值来减少最坏情况的发生概率。

思路分析2:利用最小堆(小顶堆)可以让我们高效地找到第 k 大的元素,且时间复杂度接近O(n)。

  • 使用小顶堆:维护一个大小为k的小顶堆。堆顶元素就是当前的第k大元素;
  • 构建堆:priority_queue<int, vector, greater> minHeap;创建一个小顶堆,优先队列默认是大顶堆,使用 greater 转成小顶堆
  • 更新堆
    • 从k+1个元素开始遍历数组
    • 如果当前元素比堆顶元素大,则替换堆顶元素为当前元素,并重新调整堆1。这保证堆中始终保持着当前最大的k个元素
  • 返回结果:遍历完数组后,堆顶元素就是数组中的第k大的元素

具体实现代码(详解版):

class Solution {
public:int findKthLargest(vector<int>& nums, int k) {// 创建一个小顶堆,优先队列默认是大顶堆,使用 greater<int> 转成小顶堆priority_queue<int, vector<int>, greater<int>> minHeap;// 将前 k 个元素放入小顶堆for (int i = 0; i < k; ++i) {minHeap.push(nums[i]);}// 遍历剩余的元素for (int i = k; i < nums.size(); ++i) {if (nums[i] > minHeap.top()) { // 如果当前元素比堆顶元素大minHeap.pop(); // 移除堆顶元素minHeap.push(nums[i]); // 插入当前元素}}// 返回堆顶元素,即第 k 大的元素return minHeap.top();}
};

2.前k个高频元素

在这里插入图片描述
思路分析1:用排序算法对元素按照频率由高到低进行排序,然后再取前 k 个元素

  • 统计频率:使用哈希表统计每个元素的频率;
  • 转换成频率对:将哈希表中的数据转化为一组(元素,频率)的pair,便于排序;vector<pair<int, int>> freqPairs(freqMap.begin(), freqMap.end());
    -** 排序:使用标准排序算法将这些 pair 按照频率从高到低排序。其中cmp即排序规则可以直接使用lambda表达式
    sort(freqPairs.begin(), freqPairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) { return a.second > b.second; });
  • 提取前 k 个元素:选择排序后的前 k 个元素作为结果。
    具体实现代码(详解版):
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 1. 使用哈希表统计每个元素的频率unordered_map<int, int> freqMap;for (int num : nums) {freqMap[num]++;}// 2. 将哈希表转换成 (元素, 频率) 的 pair 列表vector<pair<int, int>> freqPairs(freqMap.begin(), freqMap.end());// 3. 使用标准排序算法对频率对进行排序,按频率从高到低sort(freqPairs.begin(), freqPairs.end(), [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;});// 4. 选择前 k 个元素vector<int> result;for (int i = 0; i < k; ++i) {result.push_back(freqPairs[i].first);}return result;}
};
  • 时间复杂度:总体时间复杂度为 O(n+mlogm),在最坏情况下为 O(nlogn)。
  • 空间复杂度:O(m+k)

思路分析2:可以使用桶排序来解决这个问题,通过将出现频率相同的元素分组到对应的桶中,再按照频率从高到低提取前 k 个元素。

  • 统计频率:使用 unordered_map 统计每个元素的出现频率;
  • 创建桶:创建一个数组(桶)buckets,其中第 i 个桶存储出现频率为 i 的所有元素。数组大小设置为 nums.size() + 1,因为数组中某个元素的最大可能频率不会超过数组的长度。
  • 填充桶:根据每个元素的频率,将其加入到对应频率的桶中。
  • 按频率从高到低提取元素:从频率最高的桶(即 buckets 的末尾)向前遍历,收集桶中的元素,直到收集了 k 个元素为止。

具体实现代码(详解版):

class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {// 1. 统计每个元素的频率unordered_map<int, int> freqMap;for (int num : nums) {freqMap[num]++;}// 2. 创建桶,桶的索引是频率,桶里存的是具有该频率的所有元素int n = nums.size();vector<vector<int>> buckets(n + 1); // 每个频率可能出现的次数范围是 0 到 nfor (auto& [num, freq] : freqMap) {buckets[freq].push_back(num);}// 3. 按频率从高到低收集前 k 个高频元素vector<int> result;for (int i = n; i >= 0 && result.size() < k; --i) {for (int num : buckets[i]) {result.push_back(num);if (result.size() == k) {break;}}}return result;}
};
  • 时间复杂度:O(n);
  • 空间复杂度:O(n)

3.数据流的中位数

在这里插入图片描述
思路分析:为了实现一个能够动态获取中位数的数据结构 MedianFinder,可以利用两个堆(优先队列)来高效地维护中位数

  • 维护两个堆:使用一个大顶堆和一个小顶堆
    • 大顶堆:用于存储数据流中较小的一般数字,堆顶为较小部分的最大值;
    • 小顶堆:用于存储数据流中较大的一半数字;
  • 中位数的计算
    • 如果数据流的总长度为奇数,maxHeap的堆顶就是中位数;
    • 如果数据流的总长度为偶数,中位数是两个堆顶元素的平均值
  • 调整堆的平衡
    • 每次添加新数字时,将数字插入 maxHeap 或 minHeap 之一,并根据堆的大小调整两者的平衡,以确保 maxHeap 和 minHeap 的元素数量差最多为 1。
    • 如果 maxHeap 的大小大于 minHeap 的大小超过 1,将 maxHeap 堆顶元素移动到 minHeap。
    • 如果 minHeap 的大小大于 maxHeap,将 minHeap 堆顶元素移动到 maxHeap。

具体实现代码(详解版):

class MedianFinder {
private:priority_queue<int> maxHeap; // 大顶堆priority_queue<int, vector<int>, greater<int>> minHeap; // 小顶堆public:// 初始化MedianFinder() {}// 添加元素void addNum(int num) {// 先添加到大顶堆maxHeap.push(num);// 调整大小:如果 maxHeap 堆顶元素大于 minHeap 堆顶,将它移动到 minHeapif (!minHeap.empty() && maxHeap.top() > minHeap.top()) {minHeap.push(maxHeap.top());maxHeap.pop();}// 平衡大小:确保 maxHeap 的元素数量不小于 minHeapif (maxHeap.size() > minHeap.size() + 1) {minHeap.push(maxHeap.top());maxHeap.pop();} else if (minHeap.size() > maxHeap.size()) {maxHeap.push(minHeap.top());minHeap.pop();}}// 返回中位数double findMedian() {// 如果元素总数是奇数,返回 maxHeap 堆顶if (maxHeap.size() > minHeap.size()) {return maxHeap.top();}// 如果是偶数,返回两个堆顶的平均值return (maxHeap.top() + minHeap.top()) / 2.0;}
};
  • 时间复杂度:O(log n)
  • 空间复杂度:O(1)

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/467226.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

redis笔记-数据结构

zset zset一方面它是一个 set&#xff0c;保证了内部value 的唯一性&#xff0c;另一方面它可以给每个 value 赋予一个 score&#xff0c;代表这个 value 的排序权重。 zset的底层是由字典和跳表实现。 字典主要用来存储value和score的对应关系。跳表这个数据结构主要用来提…

day20-21之间的项目实战:若依ruoyi开发(可以跳过)

一&#xff0c;项目概述 官网文档地址&#xff1a;http://doc.ruoyi.vip/ rouyi是一个后台管理系统&#xff0c;基于经典技术组合&#xff08;spring boot&#xff0c;apache shiro&#xff0c;mybatis&#xff0c;thymeleaf&#xff09;主要是让开发者注重专注业务&#xff0…

【Android】名不符实的Window类

1.“名不符实”的Window类 Window 是一个窗口的概念&#xff0c;是所有视图的载体&#xff0c;不管是 Activity&#xff0c;Dialog&#xff0c;还是 Toast&#xff0c;他们的视图都是附加在 Window 上面的。例如在桌面显示一个悬浮窗&#xff0c;就需要用到 Window 来实现。Wi…

SDL事件相关

文章目录 事件相关的函数和数据结构用户自定义事件代码相关&#xff1a; 事件相关的函数和数据结构 SDL_WaitEvent :等待一个事件SDL_PushEvent 发送一个事件SDL_PumpEvents(): 将硬件设备产生的时间放入事件队列 &#xff0c;用于读取事件&#xff0c;在调用该函数之前&#…

机器人课程——使用TIA Portal V15博图软件进行西门子组态——带显示屏

一.打开TIA Portal V15博图软件创建项目 1.选择创建新项目 创建完成后选择PLC 二.创建完成后选择设备PLC (此处以S7-1200 1214FC DC/DC/DC 为例) 三.添加扩展板&#xff08;如有——这里以223-1BL32-0XB0为例&#xff09; 四.更改扩展版地址 五.添加触摸屏&#xff08;这里以…

【数据集】【YOLO】【目标检测】道路结冰数据集 1527 张,YOLO目标检测实战训练教程!

数据集介绍 【数据集】道路结冰数据集 1527 张&#xff0c;目标检测&#xff0c;包含YOLO/VOC格式标注。数据集中包含2种分类&#xff1a;“clear_road, ice_road”。数据集来自国内外图片网站和视频截图&#xff0c;部分数据经过数据增强处理。检测范围监控视角检测、无人机视…

【Mysql NDB Cluster 集群(CentOS 7)安装笔记一】

Mysql NDB Cluster 集群(CentOS 7)安装笔记 NDB集群核心概念 NDBCLUSTER(也称为NDB)是一个内存存储引擎,提供高可用性和数据保存功能。 NDBCLUSTER存储引擎可以配置一系列故障转移和负载平衡选项,但从集群级别的存储引擎开始是最容易的。NDB集群的NDB存储引擎包含一整套…

利用京东API接口实现商品详情数据获取与表格化展示

在电商数据分析与运营过程中&#xff0c;获取商品详情数据是至关重要的一环。京东作为国内领先的电商平台&#xff0c;其开放平台提供了丰富的API接口&#xff0c;使得开发者能够高效地获取商品信息。本文将详细介绍如何通过京东API接口获取商品详情数据&#xff0c;并将其整理…

数据结构-并查集专题(1)

一、前言 因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛&#xff0c;于是开始按专题梳理一下对应的知识点&#xff0c;先从简单入门又值得记录的内容开始&#xff0c;并查集首当其冲。 二、我的模板 虽然说是借用了jiangly鸽鸽的板子&#xff0c;但是自己也小做…

博奥龙/诊断原料抗体对

在ELISA中&#xff0c;抗体与抗原的结合精确度依赖于抗体的特异性和灵敏度。特异性较差的抗体可能导致显著的非特异性背景信号&#xff0c;而特异好但亲和力弱的抗体可能会被洗掉&#xff0c;从而产生假阴性数据。因此&#xff0c;选择合适的可避免交叉反应和确保检测结果的准确…

OceanBase详解及如何通过MySQL的lib库进行连接

OceanBase详解及如何通过MySQL的lib库进行连接 一、引言二、OceanBase概述1. 起源与发展2. 核心技术特点3. 应用场景三、OceanBase架构解析1. 系统架构2. 存储引擎3. 分布式架构四、如何使用MySQL的lib库连接OceanBase1. 前提条件2. 安装MySQL Connector/C3. 编写连接代码4. 编…

java导出word文件(手绘)

文章目录 代码细节效果图参考资料 代码细节 使用的hutool的WordUtil&#xff0c;WordUtil对poi进行封装&#xff0c;但是这一块的官方封装的很少&#xff0c;很多细节都没有。代码中是常见的绘制段落&#xff0c;标题、表格等常用api Word07Writer writer WordUtil.getWriter(…

RNN(循环神经网络)详解

1️⃣ RNN介绍 前馈神经网络&#xff08;CNN&#xff0c;全连接网络&#xff09;的流程是前向传播、反向传播和参数更新&#xff0c;存在以下不足&#xff1a; 无法处理时序数据&#xff1a;时序数据长度一般不固定&#xff0c;而前馈神经网络要求输入和输出的维度是固定的&a…

qt QHttpMultiPart详解

1. 概述 QHttpMultiPart是Qt框架中用于处理HTTP多部分请求的类。它类似于RFC 2046中描述的MIME multipart消息&#xff0c;允许在单个HTTP请求中包含多个数据部分&#xff0c;如文件、文本等。这种多部分请求在上传文件或发送带有附件的邮件等场景中非常有用。QHttpMultiPart类…

2-148 基于matlab的铣削动力学仿真

基于matlab的铣削动力学仿真&#xff0c;推导出指导加工的稳定性叶瓣图&#xff0c;并得到各主轴转速下对应的极限切深。输入不同方向刚度和切入角、切削力系数等参数&#xff0c;进行铣削动力学仿真。程序已调通&#xff0c;可直接运行。 下载源程序请点链接&#xff1a;2-14…

使用STM32F407xx的GPIO引脚实现跑马灯效果的详细步骤

1、使用Keil创建一个新工程 2、在弹出的对话框&#xff0c;填写工程的名字&#xff0c;例如工程名字为demo_led 3、为保存的工程&#xff0c;选择对应的芯片 4、为当前工程&#xff0c;添加相应的库函数 5、若库函数添加成功&#xff0c;则显示当前工程目录树 6、在当前工程目录…

_浅谈单片机的gcc优化级别__以双音频信号发生器为例

一、简介 gcc有多种优化级别&#xff0c;一般不选择的情况下&#xff0c;IDE默认是按照-Og或这-O2优化的。 以gcc编译器为例&#xff0c;浅谈一下优化级别&#xff0c;我们常见的优化一般是指gcc的-O2、-Og。除此之外&#xff0c;gcc还有-Os等一系列优化&#xff0c;链接器也有…

用JavaScript、Nodejs写一个本地tcp服务,用于前端WebSocket调试

效果&#xff1a; 准备工作&#xff1a; 新建一个文件夹&#xff0c;在根目录安装依赖&#xff1a; npm install ws express 依赖介绍&#xff1a; WS是一个轻量级、高效的WebSocket库&#xff0c;适用于Node.js环境。 express 是一个流行的Node.js Web应用程序框架。 新…

企业常见的主数据管理挑战及解决方案

在当今高度数字化的商业环境中&#xff0c;数据已成为企业决策、运营和战略规划的核心。主数据管理&#xff08;MDM&#xff09;作为管理核心业务数据的一种方式&#xff0c;帮助企业确保其关键数据在整个组织中保持一致、准确和可信。然而&#xff0c;许多企业在实施主数据管理…

Python http打印(http打印body)flask demo(http调试demo、http demo、http printer)

文章目录 代码解释 代码 # flask_http_printer.pyfrom flask import Flask, request, jsonify import jsonapp Flask(__name__)app.route(/printinfo, methods[POST]) def print_info():# 分隔符separator "-" * 60# 获取请求头headers request.headers# 获取 JS…