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

数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

数组中的第K个最大元素

  • https://leetcode.cn/problems/kth-largest-element-in-an-array/

描述

  • 给定整数数组 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 <= 1 0 5 10^5 105
  • - 1 0 4 10^4 104 <= nums[i] <= 1 0 4 10^4 104

算法实现

1 )基于js中原生sort api

const findKthLargest = function(nums, k) {return nums.sort((a,b) => b-a)[k - 1]
};
  • 这个浏览器默认提供的sort()方法,一般时间复杂度是 O(nlogn)

2 )基于堆的数据结构和堆排序的方法

// 建立最小堆类
class MinHeap {heap: number[] = [];// 交换节点位置swap(i, j) {[this.heap[i], this.heap[j]] = [this.heap[j], this.heap[i]];}// 获得父节点getParentIndex(i) {return (i - 1) >> 1;}// 获取左子节点getLeftIndex(i) {return (i << 1) + 1; // 极客写法}// 获取右子节点getRightIndex(i) {return (i << 1) + 2;}// 向上移动shiftUp(index) {// 如果到了堆顶元素,index是0,则不要再上移了if(!index) return;const parentIndex = this.getParentIndex(index)if(this.heap[parentIndex] > this.heap[index]) {this.swap(parentIndex, index)this.shiftUp(parentIndex)}}// 下移shiftDown(index) {// 边界1:如果到了堆尾元素,则不要再下移了if(index >= this.heap.length - 1) return;const size = this.size();const leftIndex = this.getLeftIndex(index);const rightIndex = this.getRightIndex(index);if (leftIndex < size && this.heap[leftIndex] < this.heap[index]) {this.swap(leftIndex, index);this.shiftDown(leftIndex);}if (rightIndex < size && this.heap[rightIndex] < this.heap[index]) {this.swap(rightIndex, index);this.shiftDown(rightIndex);}}// 插入insert(value) {this.heap.push(value);this.shiftUp(this.heap.length - 1);}// 删除堆顶pop() {// pop()方法删除数组最后一个元素并返回,赋值给堆顶this.heap[0] = this.heap.pop();// 对堆顶重新排序this.shiftDown(0);}// 获取堆顶peak() {return this.heap[0];}// 获取堆的大小size() {return this.heap.length;}
}// 实现
const findKthLargest = (nums, k) => {const h = new MinHeap();nums.forEach(n => {// 将数组元素依次插入堆中h.insert(n);// 如果堆满,则执行优胜劣汰(h.size() > k) && h.pop();})// 返回堆顶,此时就是第k大的元素return h.peak();
};
  • 关键在于这个堆的数据结构提供的 insert 方法 与 pop 方法
  • 时间复杂度:O(nlogk)
    • 一个n循环,里面还嵌套一个heap的上移递归操作logk
    • 总体:n*logk
  • 空间复杂度: O(k) 或 O(logn)
    • 堆的大小,数组的大小, k是输入的堆大小
  • 注意
    • 本题使用的是一个堆排序的算法,O(nlogn)
    • 但是还有其他排序也可以达到这个效率
    • 但是这个不符合题目的要求:时间复杂度为 O(n) 的算法

3 )基于快速排序

TODO


相关文章:

数据结构与算法之堆: Leetcode 215. 数组中的第K个最大元素 (Typescript版)

数组中的第K个最大元素 https://leetcode.cn/problems/kth-largest-element-in-an-array/ 描述 给定整数数组 nums 和整数 k&#xff0c;请返回数组中第 k 个最大的元素。请注意&#xff0c;你需要找的是数组排序后的第 k 个最大的元素&#xff0c;而不是第 k 个不同的元素。…...

SpringBoot快速入门

搭建SpringBoot工程&#xff0c;定义hello方法&#xff0c;返回“Hello SpringBoot” ②导入springboot工程需要继承的父工程&#xff1b;以及web开发的起步依赖。 ③编写Controller ④引导类就是SpringBoot项目的一个入口。 写注解写main方法调用run方法 快速构建SpringBoo…...

深度学习笔记_4、CNN卷积神经网络+全连接神经网络解决MNIST数据

1、首先&#xff0c;导入所需的库和模块&#xff0c;包括NumPy、PyTorch、MNIST数据集、数据处理工具、模型层、优化器、损失函数、混淆矩阵、绘图工具以及数据处理工具。 import numpy as np import torch from torchvision.datasets import mnist import torchvision.transf…...

高效的开发流程搭建

目录 1. 搭建 AI codebase 环境kaggle的服务器1. 搭建 AI codebase 环境 python 、torch 以及 cuda版本,对AI的影响最大。不同的版本,可能最终计算出的结果会有区别。 硬盘:PCIE转SSD的卡槽,, GPU: 软件源: Anaconda: 一定要放到固态硬盘上。 VS code 的 debug功能…...

浅谈OV SSL 证书的优势

随着网络威胁日益增多&#xff0c;保护网站和用户安全已成为每个企业和组织的重要任务。在众多SSL证书类型中&#xff0c;OV&#xff08;Organization Validation&#xff09;证书以其独特的优势备受关注。让我们深入探究OV证书的优势所在&#xff0c;为网站安全搭建坚实的防线…...

一篇博客学会系列(3) —— 对动态内存管理的深度讲解以及经典笔试题的深度解析

目录 动态内存管理 1、为什么存在动态内存管理 2、动态内存函数的介绍 2.1、malloc和free 2.2、calloc 2.3、realloc 3、常见的动态内存错误 3.1、对NULL指针的解引用操作 3.2、对动态开辟空间的越界访问 3.3、对非动态开辟内存使用free释放 3.4、使用free释放一块动态…...

【C++ techniques】虚化构造函数、虚化非成员函数

constructor的虚化 virtual function&#xff1a;完成“因类型而异”的行为&#xff1b;constructor&#xff1a;明确类型时构造函数&#xff1b;virtual constructor&#xff1a;视其获得的输入&#xff0c;可产生不同的类型对象。 //假如写一个软件&#xff0c;用来处理时事…...

蓝牙核心规范(V5.4)11.6-LE Audio 笔记之初识音频位置和通道分配

专栏汇总网址:蓝牙篇之蓝牙核心规范学习笔记(V5.4)汇总_蓝牙核心规范中文版_心跳包的博客-CSDN博客 爬虫网站无德,任何非CSDN看到的这篇文章都是盗版网站,你也看不全。认准原始网址。!!! 音频位置 在以前的每个蓝牙音频规范中,只有一个蓝牙LE音频源和一个蓝牙LE音频接…...

mysql双主+双从集群连接模式

架构图&#xff1a; 详细内容参考&#xff1a; 结果展示&#xff1a; 178.119.30.14(主) 178.119.30.15(主) 178.119.30.16(从) 178.119.30.17(从)...

嵌入式中如何用C语言操作sqlite3(07)

sqlite3编程接口非常多&#xff0c;对于初学者来说&#xff0c;我们暂时只需要掌握常用的几个函数&#xff0c;其他函数自然就知道如何使用了。 数据库 本篇假设数据库为my.db,有数据表student。 nonamescore4嵌入式开发爱好者89.0 创建表格语句如下&#xff1a; CREATE T…...

RandomForestClassifier 与 GradientBoostingClassifier 的区别

RandomForestClassifier&#xff08;随机森林分类器&#xff09;和GradientBoostingClassifier&#xff08;梯度提升分类器&#xff09;是两种常用的集成学习方法&#xff0c;它们之间的区别分以下几点。 1、基础算法 RandomForestClassifier&#xff1a;随机森林分类器是基于…...

计组——I/O方式

一、程序查询方式 CPU不断轮询检查I/O控制器中“状态寄存器”&#xff0c;检测到状态为“已完成”之后&#xff0c;再从数据寄存器取出输入数据。 过程&#xff1a; 1.CPU执行初始化程序&#xff0c;并预置传送参数&#xff1b;设置计数器、设置数据首地址。 2. 向I/O接口发…...

jsbridge实战2:Swift和h5的jsbridge通信

[[toc]] demo1: 文本通信 h5 -> app 思路&#xff1a; h5 全局属性上挂一个变量app 接收这个变量的内容关键API: navigation代理 navigationAction.request.url?.absoluteString // 这个变量挂载在 request 的 url 上 &#xff0c;在浏览器实际无法运行&#xff0c;因…...

集合原理简记

HashMap 无论在构造函数是否指定数组长度&#xff0c;进行的都是延迟初始化 构造函数作用&#xff1a; 阈值&#xff1a;threshold&#xff0c;每次<<1 &#xff0c;数组长度 负载因子 无参构造&#xff1a;设置默认的负载因子 有参&#xff1a;可以指定初始容量或…...

机器学习的超参数 、训练集、归纳偏好

一、介绍 超参数&#xff08;Hyperparameters&#xff09;和验证集&#xff08;Validation Set&#xff09;是机器学习中重要的概念&#xff0c;用于调整模型和评估其性能。 超参数&#xff1a; 超参数是在机器学习模型训练过程中需要手动设置的参数&#xff0c;而不是从数据…...

Leetcode1071. 字符串的最大公因子(三种方法,带详细解析)

Leetcode1071. 字符串的最大公因子 对于字符串 s 和 t&#xff0c;只有在 s t … t&#xff08;t 自身连接 1 次或多次&#xff09;时&#xff0c;我们才认定 “t 能除尽 s”。 给定两个字符串 str1 和 str2 。返回 最长字符串 x&#xff0c;要求满足 x 能除尽 str1 且 x 能…...

如何像人类一样写HTML之图像标签,超链接标签与多媒体标签

文章目录 前言一、图像标签1.1 什么是图像标签&#xff1f;2.2 如何使用图像标签&#xff1f; 二、超链接标签2.1 什么是超链接标签&#xff1f;2.2 如何使用超链接标签&#xff1f; 三、多媒体标签3.1 什么是多媒体标签&#xff1f;3.2 如何使用多媒体audio标签&#xff1f;3.…...

1300*C. Rumor(并查集贪心)

解析&#xff1a; 并查集&#xff0c;求每个集合的最小费用。 每次合并集合的时候&#xff0c;根节点保存当前集合最小的费用。 #include<bits/stdc.h> using namespace std; #define int long long const int N1e55; int n,m,a[N],p[N],cnt[N]; int find(int x){retur…...

python实用小代码(数据分析向)

一、python实现31省市名称替换 首先定义了一个字典province_dict&#xff0c;其中包含每个省市的无缩写名称与其标准名称之间的映射。然后&#xff0c;我们使用map()函数将每个省市名称从无缩写名称转换为标准名称&#xff0c;并将结果存储在新列省市标准名称中。 province_di…...

【oncmdmsg 鼠标】2023/8/19 上午9:50:14

2023/8/19 上午9:50:14 oncmdmsg 鼠标 2023/8/19 上午9:50:22 抱歉,您提到的 “oncmdmsg” 和 “鼠标” 是什么?请提供更多上下文信息,我将尽力帮助您。 2023/8/19 上午9:51:43 OnCmdMsg 2023/8/19 上午9:52:21 “OnCmdMsg” 是一个在 MFC (Microsoft Foundation Cla…...

大话软工笔记—需求分析概述

需求分析&#xff0c;就是要对需求调研收集到的资料信息逐个地进行拆分、研究&#xff0c;从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要&#xff0c;后续设计的依据主要来自于需求分析的成果&#xff0c;包括: 项目的目的…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者

抖音增长新引擎&#xff1a;品融电商&#xff0c;一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中&#xff0c;品牌如何破浪前行&#xff1f;自建团队成本高、效果难控&#xff1b;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

浪潮交换机配置track检测实现高速公路收费网络主备切换NQA

浪潮交换机track配置 项目背景高速网络拓扑网络情况分析通信线路收费网络路由 收费汇聚交换机相应配置收费汇聚track配置 项目背景 在实施省内一条高速公路时遇到的需求&#xff0c;本次涉及的主要是收费汇聚交换机的配置&#xff0c;浪潮网络设备在高速项目很少&#xff0c;通…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

AD学习(3)

1 PCB封装元素组成及简单的PCB封装创建 封装的组成部分&#xff1a; &#xff08;1&#xff09;PCB焊盘&#xff1a;表层的铜 &#xff0c;top层的铜 &#xff08;2&#xff09;管脚序号&#xff1a;用来关联原理图中的管脚的序号&#xff0c;原理图的序号需要和PCB封装一一…...

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅!

【把数组变成一棵树】有序数组秒变平衡BST,原来可以这么优雅! 🌱 前言:一棵树的浪漫,从数组开始说起 程序员的世界里,数组是最常见的基本结构之一,几乎每种语言、每种算法都少不了它。可你有没有想过,一组看似“线性排列”的有序数组,竟然可以**“长”成一棵平衡的二…...

STM32标准库-ADC数模转换器

文章目录 一、ADC1.1简介1. 2逐次逼近型ADC1.3ADC框图1.4ADC基本结构1.4.1 信号 “上车点”&#xff1a;输入模块&#xff08;GPIO、温度、V_REFINT&#xff09;1.4.2 信号 “调度站”&#xff1a;多路开关1.4.3 信号 “加工厂”&#xff1a;ADC 转换器&#xff08;规则组 注入…...

CVE-2023-25194源码分析与漏洞复现(Kafka JNDI注入)

漏洞概述 漏洞名称&#xff1a;Apache Kafka Connect JNDI注入导致的远程代码执行漏洞 CVE编号&#xff1a;CVE-2023-25194 CVSS评分&#xff1a;8.8 影响版本&#xff1a;Apache Kafka 2.3.0 - 3.3.2 修复版本&#xff1a;≥ 3.4.0 漏洞类型&#xff1a;反序列化导致的远程代…...

Element-Plus:popconfirm与tooltip一起使用不生效?

你们好&#xff0c;我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip&#xff0c;产品要求是两个需要结合一起使用&#xff0c;也就是鼠标悬浮上去有提示文字&#xff0c;并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...