网站的动效怎么做的/天津百度关键词推广公司
难度:中等
题目:
给定整数数组 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
解题思路:
要找到数组中第k个最大的元素,且要求时间复杂度为O(n),我们可以使用快速选择算法,这是一种基于快速排序的选择算法变种,用于找到未排序数组中的第k个元素,而无需完全排序数组。
- 选择基准:从数组中随机选择一个元素作为基准元素,或者选择数组的第一个元素、最后一个元素等作为基准。
- 分区操作:将数组分为两部分,一部分包含所有不大于基准的元素,另一部分包含所有大于基准的元素。这个操作结束后,基准元素会处于它在排序后数组中的最终位置。同时,我们也会得到基准元素在排序后数组中的索引。
- 根据基准索引判断:
- 如果基准元素的索引正好是k-1,那么基准元素就是我们要找的第k大的元素。
- 如果基准元素的索引小于k-1,说明第k大的元素在基准的右边,我们在基准的右边数组中继续执行前两步。
- 如果基准元素的索引大于k-1,说明第k大的元素在基准的左边,我们在基准的左边数组中继续执行前两步。
- 递归或迭代:重复上述过程,直到找到第k大的元素。
JavaScript实现:
function findKthLargest(nums, k) {function partition(left, right, pivotIndex) {const pivotValue = nums[pivotIndex];// 将基准元素交换到数组末尾[nums[pivotIndex], nums[right]] = [nums[right], nums[pivotIndex]];let storeIndex = left;for (let i = left; i < right; i++) {if (nums[i] > pivotValue) {[nums[storeIndex], nums[i]] = [nums[i], nums[storeIndex]];storeIndex++;}}// 将基准元素放到正确的位置[nums[right], nums[storeIndex]] = [nums[storeIndex], nums[right]];return storeIndex;}function quickSelect(left, right, kSmallest) {if (left === right) return nums[left];let pivotIndex = Math.floor(Math.random() * (right - left + 1)) + left;pivotIndex = partition(left, right, pivotIndex);if (kSmallest === pivotIndex) {return nums[kSmallest];} else if (kSmallest < pivotIndex) {return quickSelect(left, pivotIndex - 1, kSmallest);} else {return quickSelect(pivotIndex + 1, right, kSmallest);}}// 调整k为基于0的索引return quickSelect(0, nums.length - 1, nums.length - k);
}// 示例
console.log(findKthLargest([3,2,1,5,6,4], 2)); // 输出: 5,因为排序后数组为[1,2,3,4,5,6],第2大的元素是5
这段代码首先定义了partition函数来实现分区操作,然后定义了quickSelect函数来递归地执行快速选择算法。最后,findKthLargest函数调用quickSelect来找到数组中第k大的元素。注意,由于我们是从0开始计数,所以在调用quickSelect时传入的是nums.length - k。
相关文章:

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

Perl 语言的特点
Perl 语言入门学习可以涵盖多个方面,包括其特点、基本语法、高级特性以及学习资源和社区支持等。以下是一个详细的入门学习指南: 一、Perl 语言的特点 文本处理能力强:Perl 提供了丰富的字符串处理函数和正则表达式的支持,非常适…...

NLP教程:1 词袋模型和TFIDF模型
文章目录 词袋模型TF-IDF模型词汇表模型 词袋模型 文本特征提取有两个非常重要的模型: 词集模型:单词构成的集合,集合自然每个元素都只有一个,也即词集中的每个单词都只有一个。 词袋模型:在词集的基础上如果一个单词…...

【开源 Mac 工具推荐之 2】洛雪音乐(lx-music-desktop):免费良心的音乐平台
旧版文章:【macOS免费软件推荐】第6期:洛雪音乐 Note:本文在旧版文章的基础上,新更新展示了一些洛雪音乐的新功能,并且描述更为详细。 简介 洛雪音乐(GitHub 名:lx-music-desktop )…...

AMEYA360:思瑞浦推出汽车级理想二极管ORing控制器TPS65R01Q
聚焦高性能模拟芯片和嵌入式处理器的半导体供应商思瑞浦3PEAK(股票代码:688536)发布汽车级理想二极管ORing控制器TPS65R01Q。 TPS65R01Q拥有20mV正向调节功能,降低系统损耗。快速反向关断(Typ:0.39μs),在电池反向和各种汽车电气瞬…...

简约的悬浮动态特效404单页源HTML码
源码介绍 简约的悬浮动态特效404单页源HTML码,页面简约美观,可以做网站错误页或者丢失页面,将下面的代码放到空白的HTML里面,然后上传到服务器里面,设置好重定向即可 效果预览 完整源码 <!DOCTYPE html> <html><head><meta charset="utf-8&q…...

Golang 创建 Excel 文件
经常会遇到需要导出数据报表的需求,除了可以通过 encoding/csv 导出 CSV 以外,还可以使用 https://github.com/qax-os/excelize 导出 xlsx 等格式的 excel,下面封装了一个方法,支持多 sheet 的 excel 数据生成,导出按需…...

探索GitHub上的两个革命性开源项目
在数字世界中,总有一些项目能够以其创新性和实用性脱颖而出,吸引全球开发者的目光。今天,我们将深入探索GitHub上的两个令人惊叹的开源项目:Comic Translate和GPTPDF,它们不仅改变了我们处理信息的方式,还极…...

SpringBoot框架学习笔记(三):Lombok 和 Spring Initailizr
1 Lombok 1.1 Lombok 介绍 (1)Lombok 作用 简化JavaBean开发,可以使用Lombok的注解让代码更加简洁Java项目中,很多没有技术含量又必须存在的代码:POJO的getter/setter/toString;异常处理;I/O…...

【ASP.NET网站传值问题】“object”不包含“GetEnumerator”的公共定义,因此 foreach 语句不能作用于“object”类型的变量等
问题一:不允许遍历 原因:实体未强制转化 后端: ViewData["CateGroupList"] grouplist; 前端加上:var catelist ViewData["CateGroupList"] as List<Catelogue>; 这样就可以遍历catelist了 问题二:…...

Stateflow中的状态转换表
状态转换表是表达顺序模态逻辑的另一种方式。不要在Stateflow图表中以图形方式绘制状态和转换,而是使用状态转换表以表格格式表示模态逻辑。 使用状态转换表的好处包括: 易于对类列车状态机进行建模,其中模态逻辑涉及从一个状态到其邻居的转换…...

结合Redis解决接口幂等性问题
结合Redis解决接口幂等性问题 引言正文收获 引言 该问题产生背景是根据需求描述,要求对已发布的课程能进行编辑修改,并且要求能进行回滚。 幂等性问题描述:对同一个接口并发请求产生的结果是不变的。 Get 请求以及 Delete 请求天然保证幂等…...

2024算力基础设施安全架构设计与思考(免费下载)
算网安全体系是将数据中心集群、算力枢纽、一体化大数据中心三个层级的安全需求进行工程化解耦,从国家安全角度统筹设计,通过安全 服务化方式,依托威胁情报和指挥协同通道将三层四级安全体系串联贯通,达成一体化大数据安全目标。 …...

ExoPlayer架构详解与源码分析(15)——Renderer
系列文章目录 ExoPlayer架构详解与源码分析(1)——前言 ExoPlayer架构详解与源码分析(2)——Player ExoPlayer架构详解与源码分析(3)——Timeline ExoPlayer架构详解与源码分析(4)—…...

网络安全-等级保护制度介绍
一、等保发展历程 (1)1994国务院147号令 第一次提出等级保护概念,要求对信息系统分等级进行保护 (2)1999年GB17859 国家强制标准发布,信息系统等级保护必须遵循的法规 (3)2005年公安…...

【介绍下大数据组件之Storm】
🎥博主:程序员不想YY啊 💫CSDN优质创作者,CSDN实力新星,CSDN博客专家 🤗点赞🎈收藏⭐再看💫养成习惯 ✨希望本文对您有所裨益,如有不足之处,欢迎在评论区提出…...

React Hook 总结(React 萌新升级打怪中...)
1 useCallback useMemo 和 useCallback 接收的参数都是一样,都是在其依赖项发生变化后才执行,都是返回缓存的值,区别在于 useMemo 返回的是函数运行的结果,useCallback 返回的是函数。 当需要使用 useCallback 的情况通常包括以…...

Typora 1.5.8 版本安装下载教程 (轻量级 Markdown 编辑器),图文步骤详解,免费领取
文章目录 软件介绍软件下载安装步骤激活步骤 软件介绍 Typora是一款基于Markdown语法的轻量级文本编辑器,它的主要目标是为用户提供一个简洁、高效的写作环境。以下是Typora的一些主要特点和功能: 实时预览:Typora支持实时预览功能࿰…...

mac docker no space left on device
mac 上 docker 拉取镜像报错 Error response from daemon: write /var/lib/docker/tmp/docker-export-3995807640/b8464f52498789c4ebbc063d508f04e8d2586567fbffa475e3cd9afd3c5a7cf2/layer.tar: no space left on device解决: 增加 docker 虚拟磁盘大小。如下图...

单片机主控的基本电路
论文 1.复位电路 2.启动模式设置接口 3.VBAT供电接口 4.MCU 基本电路 5.参考电压选择端口...

【19】读感 - 架构整洁之道(一)
概述 《架构整洁之道》一书中有提到设计和架构的感念,它们究竟是什么?书是这么说的,它们的层次不一样,架构更“高层级”的说法,这类讨论一般都把“底层”的实现细节排除在外。而设计往往指代的具体的系统底层组织结构…...

多层全连接神经网络(三)---分类问题
问题介绍 机器学习中的监督学习主要分为回归问题和分类问题,我们之前已经讲过回归问题了,它希望预测的结果是连续的,那么分类问题所预测的结果就是离散的类别。这时输入变量可以是离散的,也可以是连续的,而监督学习从数…...

签名优化:请求数据类型不是`application/json`,将只对随机数进行签名计算,例如文件上传接口。
文章目录 I 签名进行请求数据类型类型判断1.1 常见的ContentType1.2 签名切面处理1.3 文件上传案例1.4 处理接口信息背景: 文件上传接口的请求数据类型通常为multipart/form-data,方便携带文本域和使用接口文档进行调试。 如果携带JSON数据,不方便调试接口。 前端数据也要特…...

PostgreSQL的Json数据类型如何使用
PostgreSQL中的JSON数据类型提供了一种灵活的方式来存储JSON(JavaScript Object Notation)数据。JSON是一种轻量级的数据交换格式,易于人阅读和编写,同时也易于机器解析和生成。在PostgreSQL中,你可以使用JSON和JSONB&…...

SpringData JPA Mongodb 查询部分字段
JPA 网上用的好像不多,找了好多材料以后最终找了这个可行的方案: Query(fields "{tender_id:1,_id:0}")List<MGPltTender> findByTenderIdIsNotNull(PageRequest pageRequest); 调用: Sort sort Sort.by(popularType.getC…...

NC65 设置下拉列表框值
NC65 设置下拉列表框值,如人员任职信息的异动事件: // 只有在入职登记时,才为异动事件下拉框过滤掉【离职】和【离职后变动】两个item DefaultConstEnum[] enumItems initTransevent(); BillItem item getBillCardPanel().getHeadItem(Psn…...

小阿轩yx-高性能内存对象缓存
小阿轩yx-高性能内存对象缓存 案例分析 案例概述 Memcached 是一款开源的高性能分布式内存对象缓存系统用于很多网站提高访问速度,尤其是需要频繁访问数据的大型网站是典型的 C/S 架构,需要构建 Memcached 服务器端与 Memcached API 客户端用 C 语言…...

华中师范大学学报人文社会科学版
一、《华中师范大学学报(人文社会科学版)》是国家教育部主管、华中师范大学主办的人文社会科学综合性学术期刊。本刊用稿以质量为标准,不分内稿外稿。文稿一经发表,即付报酬,不收版面费。 二、根据教育部和新闻出版总署颁发的社会科学学报编排规范,来稿应注意以下各项: 1. 题…...

CI/CD的node.js编译报错npm ERR! network request to https://registry.npmjs.org/
1、背景: 在维护paas云平台过程中,有研发反馈paas云平台上的CI/CD的前端流水线执行异常。 2、问题描述: 流水线执行的是前端编译,使用的是node.js环境。报错内容如下: 2024-07-18T01:23:04.203585287Z npm ERR! code E…...

用ssh tunnel的方式设置 AWS DocumentDB 公网访问
AWS DocumentDB的设定是只允许VPC内进行访问的,同时官方文档给了步骤,通过ssh tunnel的方式,可以从公网,或者从VPC外的网络,对DocumentDB进行访问。 我阅读了AWS官方文档并测试了这个步骤,如下是详细的步骤…...