堆排序:力扣215.数组中的第K个大元素

一、问题描述

在一个整数数组 nums 中,需要找出第 k 个最大的元素。这里要注意,我们要找的是数组排序后的第 k 个最大元素,而不是第 k 个不同的元素。例如,对于数组 [3,2,1,5,6,4],当 k = 2 时,第 2 个最大的元素是 5。

二、解决思路

我们可以使用大顶堆排序算法来解决这个问题。大顶堆是一种完全二叉树,其中每个节点的值都大于或等于其子节点的值。通过构建大顶堆,我们可以将数组中的元素按照从大到小的顺序排列,然后取出第 k 个元素即可。

三、代码实现

/*** @param {number[]} nums* @param {number} k* @return {number}*/
var findKthLargest = function(nums, k) {let n = nums.length;// 以大顶堆为做法,其实堆就只是通过完全二叉树的性质,在数组中进行操作// 如果数组以 0 开头,那么节点 i 的左节点为 2 * i + 1,右节点为 2 * i + 2// max 表示维护的是 0 到 max 这部分的顺序,max 到 n - 1 这部分已经形成顺序了// i 表示维护的是以 i 为父节点,它和它子节点的大顶堆关系function heapify(max, i) {let lastMax = i;let lson = 2 * i + 1;let rson = 2 * i + 2;// 比较左子节点和父节点的大小,如果左子节点更大,则更新 lastMaxif (lson < max && nums[lson] > nums[lastMax]) {lastMax = lson;}// 比较右子节点和当前最大节点的大小,如果右子节点更大,则更新 lastMaxif (rson < max && nums[rson] > nums[lastMax]) {lastMax = rson;}// 如果 lastMax 不等于 i,说明需要交换父节点和最大子节点的位置if (lastMax != i) {let temp = nums[lastMax];nums[lastMax] = nums[i];nums[i] = temp;// 递归调用 heapify 函数,继续维护以 lastMax 为根节点的子树的大顶堆性质heapify(max, lastMax);}}// 大顶堆排序的入口function heap_sort() {// 首先要从最后一个非叶子节点开始建立大顶堆for (let i = Math.floor(n / 2 - 1); i >= 0; i--) {heapify(n, i);}// 然后呢,我们已经形成大顶堆了,现在要把他们完全排序// 怎么做呢,先把 [0] 与 [n - 1] 对调,这样 [n - 1] 的数就变成了最大的数// 接下来再维护 0 到 n - 2 之间的大顶堆,从堆顶 0 依次维护下去,数组 nums 就变成从小到大顺序的for (let i = n - 1; i >= 0; i--) {//这里是为了完整的堆排序,如果只是要获取第k大的//直接if(n==n-k-1) return nums[n-k]就行,无需再继续了let temp = nums[i];nums[i] = nums[0];nums[0] = temp;heapify(i, 0);}}heap_sort();console.log(nums);return nums[n - k];
};

四、代码详细解释

1. findKthLargest 函数

这个函数是整个算法的入口,它接收两个参数:nums 数组和 k。首先,我们获取数组的长度 n,然后调用 heap_sort 函数对数组进行排序,最后返回排序后数组的第 n - k 个元素,即为第 k 个最大的元素。

2. heapify 函数

这个函数用于维护以 i 为父节点的子树的大顶堆性质。具体步骤如下:

  • 初始化 lastMax 为 i,表示当前最大节点为父节点。
  • 计算左子节点的索引 lson = 2 * i + 1 和右子节点的索引 rson = 2 * i + 2
  • 比较左子节点和父节点的大小,如果左子节点更大,则更新 lastMax 为左子节点的索引。
  • 比较右子节点和当前最大节点的大小,如果右子节点更大,则更新 lastMax 为右子节点的索引。
  • 如果 lastMax 不等于 i,说明需要交换父节点和最大子节点的位置,然后递归调用 heapify 函数,继续维护以 lastMax 为根节点的子树的大顶堆性质。

3. heap_sort 函数

这个函数是大顶堆排序的入口,具体步骤如下:

  • 构建大顶堆:从最后一个非叶子节点开始,依次调用 heapify 函数,将数组转换为大顶堆。最后一个非叶子节点的索引为 Math.floor(n / 2 - 1)
  • 排序:将堆顶元素(即数组的第一个元素)与数组的最后一个元素交换,然后将堆的大小减 1,再次调用 heapify 函数维护堆的性质。重复这个过程,直到堆的大小为 1,此时数组就已经按从小到大的顺序排序好了。

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

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

相关文章

Qt-ZMQ的使用补充(pub-sub)

之前写过一篇Qt使用ZMQ的博客Qt网络编程-ZMQ的使用&#xff0c;本文是其的补充部分。 Linux上编译使用 首先这次实在Linux上进行演示&#xff0c;下载zmq源码&#xff0c;安装cmake&#xff0c;使用cmake进行编译。下载之后解压&#xff1a; 输入命令&#xff1a; cd ..mkdi…

一款基于Python的从常规文档里提取图片的简单工具开发方案

一款基于Python的从常规文档里提取图片的简单工具开发方案 1. 环境准备 安装必需库 pip install python-docx PyMuPDF openpyxl beautifulsoup4 pillow pip install pdfplumber # PDF解析备用方案 pip install tk # Python自带&#xff0c;无需安装工具选择 开发环…

日志存储与分析

日志是系统运行的详细记录&#xff0c;包含各种事件发生的主体、时间、位置、内容等关键信息。出于运维可观测、网络安全监控及业务分析等多重需求&#xff0c;企业通常需要将分散的日志采集起来&#xff0c;进行集中存储、查询和分析&#xff0c;以进一步从日志数据里挖掘出有…

cyberstrikelab lab2

lab2 重生之我是渗透测试工程师&#xff0c;被公司派遣去测试某网络的安全性。你的目标是成功获取所有服务器的权限&#xff0c;以评估网络安全状况。 先扫一下 ​ ​ 192.168.10.10 ​ ​ 骑士cms 先找后台路径 http://192.168.10.10:808/index.php?madmin&cind…

1.5.2 掌握Scala内建控制结构 - 块表达式

Scala的块表达式使用{}包裹语句组&#xff0c;单行语句不加分号&#xff0c;多语句用分号隔开。块表达式的结果是最后一行语句的值&#xff0c;无需单独写return。若无执行结果&#xff0c;则返回Unit对象&#xff08;类似Java的void&#xff09;。例如&#xff0c;有返回值时&…

VSCode + CMake

参考文献&#xff1a; 如何用 GCC, CMake 和 Make 编译C/C代码Windows 上的 Linux 子系统&#xff1a;WSLWSL&#xff1a;桌面 UI 远程连接 RDP 配置 VScode 文章目录 CMake 配置VSCode 配置launch.jsontask.jsonc_cpp_properties.json CMake 配置 编写如下的 CmakeLists.t…

【软考-架构】7、系统配置与性能评价

✨资料&文章更新✨ GitHub地址&#xff1a;https://github.com/tyronczt/system_architect 文章目录 性能指标&#x1f4af;考试真题第一题第二题 性能评价方法&#x1f4af;考试真题第一题第二题 阿姆达尔解决方法考试真题 性能指标 对计算机评价的主要性能指标有&#x…

STC89C52单片机学习——第20节: [8-2]串口向电脑发送数据电脑通过串口控制LED

写这个文章是用来学习的,记录一下我的学习过程。希望我能一直坚持下去,我只是一个小白,只是想好好学习,我知道这会很难&#xff0c;但我还是想去做&#xff01; 本文写于&#xff1a;2025.03.15 51单片机学习——第20节: [8-2]串口向电脑发送数据&电脑通过串口控制LED 前言…

java简单基础学习

目录 简单5位验证码快捷键的使用 评委打分5个评委 去掉一个最高分和一个最低分 取平均分 抢红包出现数组越界java​编辑 双色球系统--之蒟蒻学习 简单5位验证码快捷键的使用 题目意思做个验证码 //生成一个5位数的验证码 //前四位是字母,大小字母都可以 //最后一位要是数字…

前端学习记录:解决路由缓存问题

问题描述&#xff1a;响应路由参数的变化&#xff0c;使用带有参数的路由时需要注意的是&#xff0c;当用户从 /users/johnoy 导航到 /users/jolyne 时&#xff0c;相同的组件实例将会被重复使用。因为两个路由都渲染同个组件&#xff0c;比起销毁再创建&#xff0c;复用则显得…

Leetcode-1278.Palindrome Partitioning III [C++][Java]

目录 一、题目描述 二、解题思路 【C】 【Java】 Leetcode-1278.Palindrome Partitioning IIIhttps://leetcode.com/problems/palindrome-partitioning-iii/description/1278. 分割回文串 III - 力扣&#xff08;LeetCode&#xff09;1278. 分割回文串 III - 给你一个由小写…

deepseek GRPO算法保姆级讲解(数学原理+源码解析+案例实战)

文章目录 什么是GRPO群组形成(Group Formation):让大模型创建多种解决方案偏好学习(Preference Learning)&#xff1a;让大模型理解何为好的解答组内相对优势 优化(optimization): 让大模型从经验中学习(learning from experience)目标函数 GRPO算法的伪码表示GRPO算法的局限与…

【Linux我做主】基础命令完全指南上篇

Linux基础命令完全指南【上篇】 Linux基础命令完全指南github地址前言命令行操作的引入Linux文件系统树形结构的根文件系统绝对路径和相对路径适用场景Linux目录下的隐藏文件 基本指令目录和文件相关1. ls2. cd和pwdcdpwd 3. touch4. mkdir5. cp6. mv移动目录时覆盖写入的两种特…

自然语言秒转SQL—— 免费体验 OB Cloud Text2SQL 数据查询

在数据驱动决策的今天&#xff0c;企业急需从庞大业务数据中提炼信息&#xff0c;获取深度洞察。然而&#xff0c;面对海量数据&#xff0c;业务人员往往因缺乏SQL专业技能而难以快速查询和分析所需信息&#xff0c;频繁求助于BI部门不仅抬高了企业的沟通与时间成本&#xff0c…

鸿蒙next 多行文字加图片后缀实现方案

需求 实现类似iOS的YYLabel之类的在文字后面加上图片作为后缀的样式&#xff0c;多行时文字使用…省略超出部分&#xff0c;但必须保证图片的展现。 系统方案 在当前鸿蒙next系统提供的文字排版方法基本没有合适使用的接口&#xff0c;包括imagespan和RichEditor,根据AI的回…

C语言基础知识04---指针

目录 1、指针 1.1 指针概念 1.2 指针的大小 1.3 指针的定义 1.4 多级指针 1.5 指针的初始化 1.6 指针的使用 1.7 类型转换 1.8 大小端 1.9 地址偏移 1.10 指针常量&&常量指针 1.11 指针数组&&数组指针 1、指针 1.1 指针概念 指针保存地址&#xff…

spring boot 发送邮件验证码

一、前置需求 1、准备邮箱 2、登录授权码 qq邮箱在–>设置–>账号POP3/IMAP/SMTP/Exchange/CardDAV/CalDAV服务 开启服务 二、发送邮件 1、简单邮件 包含邮件标题、邮件正文 2、引入mail启动器 <dependency><groupId>org.springframework.boot</groupI…

Spring Cloud Config - 动态配置管理与高可用治理

引言&#xff1a;为什么需要配置中心&#xff1f; 在微服务架构中&#xff0c;配置管理面临分散化、多环境、动态更新三大挑战。传统基于application.yml等配置文件的硬编码方式&#xff0c;导致以下问题&#xff1a; • 环境差异&#xff1a;开发、测试、生产环境配置混杂&a…

[网络][tcp协议]:tcp报头

tcp(传输控制协议)是一种面向字节流的传输层协议,相较于udp协议,tcp能保证传输数据的可靠性与准确性,tcp也是目前最常见的传输层协议 本文主要介绍tcp报头各个字段的含义与用途 注:保留6位和6位标记位是目前最普遍的写法,在我查资料时,发现有一些拓展情况,会在后文细说 最简单的…

【sklearn 01】人工智能概述

一、人工智能&#xff0c;机器学习&#xff0c;深度学习 人工智能指由人类制造出的具有智能的机器。这是一个非常大的范围&#xff0c;长远目标是让机器实现人工智能&#xff0c;但目前我们仍处在非常初始的阶段&#xff0c;甚至不能称为智能 机器学习是指通过数据训练出能完成…