当前位置: 首页 > 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…...

400字节的前端奇迹:TinyEditor如何重新定义微型代码编辑体验

400字节的前端奇迹&#xff1a;TinyEditor如何重新定义微型代码编辑体验 【免费下载链接】TinyEditor A functional HTML/CSS/JS editor in less than 400 bytes 项目地址: https://gitcode.com/gh_mirrors/ti/TinyEditor 在前端开发的世界里&#xff0c;我们常常被功能…...

10大好用的班组建设系统盘点!助力企业高效开展班组建设

在2026年数字化转型的深水区&#xff0c;班组建设系统已成为企业夯实基层管理、提升执行力的核心引擎。面对市场上琳琅满目的工具&#xff0c;如何筛选出真正好用的班组建设系统&#xff0c;切实助力企业高效开展班组建设&#xff0c;是管理者面临的首要难题。本文深度盘点10大…...

Vite - vite.config.js 的一些配置(base、resolve、server)

一、base 1、基本介绍 base 用于设置开发或生产环境服务的公共基础路径 类型&#xff1a;string默认值&#xff1a;/2、演示 部署在根路径 base: /// 例如&#xff0c;https://example.com/<!-- 此时生成的 HTML 中的资源引用会变为如下 --><script src"/assets/…...

恶意代码分析——基础技术篇

恶意代码分析——基础技术篇 文章目录 恶意代码分析目的恶意代码分析方法恶意代码种类恶意代码静态分析 环境在线反病毒引擎获取哈希值&#xff08;certutil-hanshfile path MD5&#xff09;查找字符串hive string ida火绒剑加壳&查壳 文件加壳使用PEiD检测加壳 导入导出…...

因果模型评估完全手册:Python指标与验证方法详解

因果模型评估完全手册&#xff1a;Python指标与验证方法详解 【免费下载链接】python-causality-handbook 项目地址: https://gitcode.com/gh_mirrors/py/python-causality-handbook 在数据分析和决策科学领域&#xff0c;因果推断模型的评估是确保模型可靠性与实用性的…...

在Jetson Nano上构建海康威视相机Docker镜像:从SDK集成到Python应用部署

1. 环境准备与基础配置 在Jetson Nano上构建海康威视相机Docker镜像的第一步&#xff0c;是确保硬件和基础软件环境就绪。我建议从官方渠道下载最新的JetPack SDK&#xff0c;这个工具包包含了CUDA、cuDNN等深度学习推理必需的组件。安装完成后&#xff0c;记得运行nvidia-smi命…...

如何利用多渠道SEO推广提高网站流量

<h2>多渠道SEO推广&#xff1a;如何提高网站流量</h2> <p>在当前竞争激烈的互联网环境中&#xff0c;网站流量是衡量网站成功与否的重要指标之一。如何利用多渠道SEO推广提高网站流量&#xff0c;成为了每一个网站运营者关注的焦点。本文将从问题分析、原因说…...

Flutter Gradle插件迁移指南:从apply script到声明式plugins的实践

1. 为什么需要迁移到声明式plugins块 最近在维护一个Flutter项目时&#xff0c;我发现每次构建Android端都会弹出一个黄色警告&#xff1a;"You are applying Flutters app_plugin_loader Gradle plugin imperatively using the apply script method..."。这个警告看…...

六足机器人如何自己“学会”走路?手把手教你用Q-learning实现自适应步态

六足机器人如何自己“学会”走路&#xff1f;手把手教你用Q-learning实现自适应步态 想象一下&#xff0c;当你把一只六足机器人放在崎岖不平的地面上时&#xff0c;它能够像昆虫一样迅速调整自己的步伐&#xff0c;找到最稳定的行走方式。这种看似简单的行为背后&#xff0c;隐…...

Java 25并发模型重构实战:用StructuredTaskScope替代CompletableFuture组合的4种高危写法(附JFR火焰图对比)

第一章&#xff1a;Java 25结构化并发演进全景图Java 25正式将结构化并发&#xff08;Structured Concurrency&#xff09;从孵化阶段&#xff08;JEP 428、437、444&#xff09;升级为标准特性&#xff0c;标志着JVM平台在并发模型抽象上完成关键跃迁。该机制通过作用域&#…...