当前位置: 首页 > news >正文

【leetcode】堆习题

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

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {let arr = new MinHeap()nums.forEach(item => {arr.insert(item)if (arr.size() > k) {arr.pop()}})return arr.peek()
};class MinHeap {constructor() {this.heap = []}// 换位置swap(i1, i2) {let temp = this.heap[i1]this.heap[i1] = this.heap[i2]this.heap[i2] = temp}// 找到父节点getParentIndex(index) {return Math.floor((index - 1) / 2)}// 上(前)移操作up(index) {if (index === 0) returnconst parentIndex = this.getParentIndex(index)if (this.heap[parentIndex] > this.heap[index] ) {this.swap( parentIndex, index )this.up(parentIndex)}}// 找到左侧子节点getLeftIndex(index) {return index * 2 + 1}// 找到右侧子节点getRigthIndex(index) {return index * 2 + 2}// 下(后)移操作down(index) {const leftIndex = this.getLeftIndex(index)const rightIndex = this.getRigthIndex(index)if (this.heap[leftIndex] < this.heap[index]) {this.swap(leftIndex, index)this.down(leftIndex)}if (this.heap[rightIndex] < this.heap[index]) {this.swap(rightIndex, index)this.down(rightIndex)}}// 添加元素insert( value ) {this.heap.push(value)this.up( this.heap.length-1 )}// 删除堆顶pop() {this.heap[0] = this.heap.pop()this.down(0)}// 获取堆顶peek() {return this.heap[0]}// 获取堆长度size() {return this.heap.length}
}

LCR 159. 库存管理 III(计数排序
仓库管理员以数组 stock 形式记录商品库存表,其中 stock[i] 表示对应商品库存余量。请返回库存余量最少的 cnt 个商品余量,返回 顺序不限。
示例 1:
输入:stock = [2,5,7,4], cnt = 1
输出:[2]
示例 2:
输入:stock = [0,2,3,6], cnt = 2
输出:[0,2] 或 [2,0]
提示:
0 <= cnt <= stock.length <= 10000
0 <= stock[i] <= 10000

/*** @param {number[]} stock* @param {number} cnt* @return {number[]}*/// 原生API
var inventoryManagement = function(stock, cnt) {return stock.sort((a,b) => a-b).slice(0, cnt)
};// 计数排序 用空间换时间
var inventoryManagement = function(stock, cnt) {return countingSort(stock, cnt, 10000)
};
let countingSort = (arr, k, maxValue) => {let bucket = new Array(maxValue),sortedIndex = 0,arrLen = arr.lengthbucketLength = maxValue// 生成 bucket. 示例:stock = [2,5,7,4],则 bucket = [0, 0, 1, 0, 1, 1, 0, 1]for (let i = 0; i < arrLen; i++) {if (!bucket[arr[i]]) {bucket[arr[i]] = 0}bucket[arr[i]]++}let res = []for (let j = 0; j < bucketLength; j++) {while (bucket[j]-- > 0 && sortedIndex < k) {res[sortedIndex++] = j}if (sortedIndex === k) {break}}return res
}

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 个高频元素的集合是唯一的


相关文章:

【leetcode】堆习题

215.数组中的第K个最大元素 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。 请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。 你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输…...

前端大模型入门:编码(Tokenizer)和嵌入(Embedding)解析 - llm的输入

LLM的核心是通过对语言进行建模来生成自然语言输出或理解输入,两个重要的概念在其中发挥关键作用&#xff1a;Tokenizer 和 Embedding。本篇文章将对这两个概念进行入门级介绍,并提供了针对前端的js示例代码&#xff0c;帮助读者理解它们的基本原理/作用和如何使用。 1. 什么是…...

一文读懂 JS 中的 Map 结构

你好&#xff0c;我是沐爸&#xff0c;欢迎点赞、收藏、评论和关注。 上次聊了 Set 数据结构&#xff0c;今天我们聊下 Map&#xff0c;看看它与 Set、与普通对象有什么区别&#xff1f;下面直接进入正题。 一、Set 和 Map 有什么区别&#xff1f; Set 是一个集合&#xff0…...

C++校招面经(二)

欢迎关注 0voice GitHub 6、 C 和 Java 区别&#xff08;语⾔特性&#xff0c;垃圾回收&#xff0c;应⽤场景等&#xff09; 指针&#xff1a; Java 语⾔让程序员没法找到指针来直接访问内存&#xff0c;没有指针的概念&#xff0c;并有内存的⾃动管理功能&#xff0c;从⽽…...

Python Web 面试题

1 Web 相关 get 和 post 区别 get&#xff1a; 请求数据在 URL 末尾&#xff0c;URL 长度有限制 请求幂等&#xff0c;即无论请求多少次&#xff0c;服务器响应始终相同&#xff0c;这是因为 get 至少获取资源&#xff0c;而不修改资源 可以被浏览器缓存&#xff0c;以便以后…...

java日志框架之JUL(Logging)

文章目录 一、JUL简介1、JUL组件介绍 二、Logger快速入门三、Logger日志级别1、日志级别2、默认级别info3、原理分析4、自定义日志级别5、日志持久化&#xff08;保存到磁盘&#xff09; 三、Logger父子关系四、Logger配置文件 一、JUL简介 JUL全程Java Util Logging&#xff…...

ARM驱动学习之PWM

ARM驱动学习之PWM 1.分析原理图&#xff1a; GPD0_0 XpwmTOUT0定时器0 2.定时器上的资源&#xff1a; 1.5组32位定时器 2.定时器产生内部中断 3.定时器0&#xff0c;1&#xff0c;2可编程实现pwm 4.定时器各自分频 5.TCN--,TCN TCMPBN 6.分频器 24-2 7.24.3.4 例子&#xff1…...

我的AI工具箱Tauri版-VideoClipMixingCut视频批量混剪

本教程基于自研的AI工具箱Tauri版进行VideoClipMixingCut视频批量混剪。 VideoClipMixingCut视频批量混剪 是自研AI工具箱Tauri版中的一款强大工具&#xff0c;专为自动化视频批量混剪设计。该模块通过将预设的解说文稿与视频素材进行自动拼接生成混剪视频&#xff0c;适合需要…...

postgres_fdw访问存储在外部 PostgreSQL 服务器中的数据

文章目录 一、postgres_fdw 介绍二、安装使用示例三、成本估算四、 远程执行选项执行计划无法递推解决 参考文件&#xff1a; 一、postgres_fdw 介绍 postgres_fdw 模块提供外部数据包装器 postgres_fdw&#xff0c;可用于访问存储在外部 PostgreSQL 服务器中的数据。 此模块…...

什么是3D展厅?有何优势?怎么制作3D展厅?

一、什么是3D展厅&#xff1f; 3D展厅是一种利用三维技术构建的虚拟展示空间。它借助虚拟现实&#xff08;VR&#xff09;、增强现实&#xff08;AR&#xff09;等现代科技手段&#xff0c;将真实的展示空间数字化&#xff0c;呈现出逼真、立体、沉浸的展示效果。通过3D展厅&a…...

Linux下的CAN通讯

CAN总线 CAN总线简介 CAN&#xff08;Controller Area Network&#xff09;总线是一种多主从式 <font color red>异步半双工串行 </font> 通信总线&#xff0c;它最早由Bosch公司开发&#xff0c;用于汽车电子系统。CAN总线具有以下特点&#xff1a; 多主从式&a…...

【Python】pip安装加速:使用国内镜像源

【Python】pip安装加速&#xff1a;使用国内镜像源 零、使用命令行设置 设置全局镜像源 随便使用下面任一命令即可&#xff01; 阿里云&#xff1a; pip config set global.index-url https://mirrors.aliyun.com/pypi/simple/豆瓣&#xff1a; pip config set global.in…...

SpringBoot lombok(注解@Getter @Setter)

SpringBoot lombok(注解Getter Setter) 使用lombok注解的方式&#xff0c;在编译生成的字节码文件中就会存在setter/getter等方法&#xff0c;减少代码量&#xff0c;方便了代码的维护 添加依赖 <dependency><groupId>org.projectlombok</groupId><artif…...

descrTable常用方法

descrTable 为 R 包 compareGroups 的重要函数&#xff0c;有关该函数以及 compareGroups 包的详细内容见&#xff1a;R包compareGroups详细用法 加载包和数据 library(compareGroups)# 加载 REGICOR 数据&#xff08;横断面&#xff0c;从不同年份纳入&#xff0c;每个变量有…...

回归预测 | Matlab实现ReliefF-XGBoost多变量回归预测

回归预测 | Matlab实现ReliefF-XGBoost多变量回归预测 目录 回归预测 | Matlab实现ReliefF-XGBoost多变量回归预测效果一览基本介绍程序设计参考资料 效果一览 基本介绍 1.ReliefF-xgboost回归预测代码&#xff0c;对序列数据预测性能相对较高。首先通过ReleifF对输入特征计算权…...

年度最强悬疑美剧重磅回归,一集比一集上头

纽约的夜晚&#xff0c;平静被一声枪响打破&#xff0c;一场离奇的谋杀案悄然上演。《大楼里只有谋杀》正是围绕这样一桩扑朔迷离的案件展开的。三位主角&#xff0c;赛琳娜戈麦斯饰演的梅宝、史蒂夫马丁饰演的查尔斯、马丁肖特饰演的奥利弗&#xff0c;这些性格迥异的邻居因为…...

AI一点通: 简化大数据与深度学习工作流程, Apache Spark、PyTorch 和 Mosaic Streaming

在大数据和机器学习飞速发展的领域中&#xff0c;数据科学家和机器学习工程师经常面临的一个挑战是如何桥接像 Apache Spark 这样的强大数据处理引擎与 PyTorch 等深度学习框架。由于它们在架构上的固有差异&#xff0c;利用这两个系统的优势可能令人望而生畏。本博客介绍了 Mo…...

Python知识点:深入理解Python的模块与包管理

开篇&#xff0c;先说一个好消息&#xff0c;截止到2025年1月1日前&#xff0c;翻到文末找到我&#xff0c;赠送定制版的开题报告和任务书&#xff0c;先到先得&#xff01;过期不候&#xff01; 深入理解Python的模块与包管理 Python的模块和包是代码组织、复用和分发的基本…...

倒排索引(反向索引)

倒排索引&#xff08;Inverted Index&#xff09;是搜索引擎和数据库管理系统中常用的一种数据结构&#xff0c;用于快速检索文档集合中的文档。在全文搜索场景中&#xff0c;倒排索引是一种非常高效的手段&#xff0c;因为它能够快速定位到包含特定关键词的所有文档。 1、基本…...

openCV的python频率域滤波

在OpenCV中实现频率域滤波通常涉及到傅里叶变换(Fourier Transform)和其逆变换(Inverse Fourier Transform)。傅里叶变换是一种将图像从空间域转换到频率域的数学工具,这使得我们可以更容易地在图像的频域内进行操作,如高通滤波、低通滤波等。 下面,我将提供一个使用Py…...

提升大语言模型对话体验:text-generation-webui全流程优化指南

提升大语言模型对话体验&#xff1a;text-generation-webui全流程优化指南 【免费下载链接】text-generation-webui A Gradio web UI for Large Language Models. Supports transformers, GPTQ, AWQ, EXL2, llama.cpp (GGUF), Llama models. 项目地址: https://gitcode.com/G…...

反线性学习—— 不是“按顺序学完教材”,是“围绕目标把知识长出来”

反线性学习—— 不是“按顺序学完教材”&#xff0c;是“围绕目标把知识长出来”在传统的学习习惯中&#xff0c;我们往往有一种 “进度条强迫症”&#xff1a;只要书看完了、课听完了、笔记记满了&#xff0c;就觉得自己“学完了”。 但现实往往很残酷&#xff1a;当你合上书本…...

企业数字化转型基石:全面认识4A企业架构数据架构方案

数据架构是企业架构中连接业务、应用与技术的桥梁&#xff0c;通过数据资产目录厘清家底&#xff0c;数据标准统一语言&#xff0c;数据模型指导开发&#xff0c;数据分布拉通业务流&#xff0c;从而提升数据质量与运作效率&#xff0c;支撑业务决策与系统建设。 统一语言&…...

别再只盯着PID了!用STM32 HAL库的PWM差速,让你的5路红外寻迹小车先跑起来

别再只盯着PID了&#xff01;用STM32 HAL库的PWM差速&#xff0c;让你的5路红外寻迹小车先跑起来 第一次做红外寻迹小车时&#xff0c;我也被各种PID教程绕得晕头转向。直到有天深夜调试时&#xff0c;我突然意识到——为什么非要一开始就用复杂的PID算法&#xff1f;对于简单…...

OpenClaw 生态全景图——AI 助理如何改变工作方式

OpenClaw 生态全景图——AI 助理如何改变工作方式摘要&#xff1a;2026 年&#xff0c;AI 助理从"玩具"变成"工具"。本文带你了解 OpenClaw 生态系统的完整布局&#xff0c;看它如何连接微信、飞书、钉钉等主流平台&#xff0c;以及企业和个人如何利用它提…...

Java基础-初识Java

SUN公司是一家什么样的公司? 美国SUN(Stanford University Network)公司在中国大陆的正式中文名为“太阳计算机系统&#xff08;中国&#xff09;有限公司”在中国台湾中文名为“升 阳电脑公司”。 Java为什么被发明? Green项目。应用环境&#xff1a;像电视盒这样的消费类电…...

别再让反归一化坑了你!用TensorFlow+Keras做LSTM时序预测的完整避坑指南

LSTM时序预测中的归一化陷阱&#xff1a;从原理到实战的完整解决方案 当你兴奋地看着训练好的LSTM模型在测试集上展现出漂亮的损失曲线&#xff0c;却在最后一步——将预测值还原为业务可理解的单位时栽了跟头&#xff0c;这种挫败感我深有体会。归一化是时序预测的标准预处理步…...

薛定谔共价对接实战:如何为你的靶点蛋白快速找到‘锁死’它的共价抑制剂?

薛定谔共价对接实战&#xff1a;靶点蛋白的共价抑制剂高效筛选策略 药物研发领域正经历一场静默革命——共价抑制剂从曾经的"危险分子"摇身变为现代药物设计的明星。与传统可逆抑制剂不同&#xff0c;共价抑制剂能与靶点蛋白形成稳定的共价键&#xff0c;实现近乎不可…...

深入解析振动传感器:从原理到应用的全面指南

1. 振动传感器入门&#xff1a;从"感觉"到"测量"的跨越 你有没有想过&#xff0c;为什么手机横屏时画面会自动旋转&#xff1f;为什么智能手环能记录你的步数&#xff1f;这些看似简单的功能背后&#xff0c;都离不开一个关键元件——振动传感器。作为工业…...

从‘猫狗大战’到医疗影像:LRP(逐层相关性传播)如何帮医生看懂AI的‘诊断思路’?

从‘猫狗大战’到医疗影像&#xff1a;LRP如何成为医生与AI的翻译官 当一位放射科医生第一次看到AI系统标注的肺结节"恶性概率92%"时&#xff0c;他的反应不是赞叹&#xff0c;而是皱眉&#xff1a;"它凭什么这么判断&#xff1f;"这种场景正在全球各大医院…...