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

算法题：数组中的第 K 个最大元素（中等难度）

news 来源：原创 2025/9/11 13:59:40

一、题目

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1：

输入：nums = [3,2,1,5,6,4], k = 2
输出：5

示例 2：

输入：nums = [3,2,3,1,2,4,5,5,6], k = 4
输出：4

提示：

1 <= k <= nums.length <= 104
-104 <= nums[i] <= 104

二、解法

1、直接排序，把重复的值过滤掉，放在一个数组里，然后取第二大的值，简单粗暴

def quick_sort(arr):#快速排序if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)def sort_and_deduplicate(nums):# 使用 set 去重unique_nums = list(set(nums))# 对去重后的数组进行排序return quick_sort(unique_nums)# 示例
nums = [3, 2, 1, 3, 5, 6, 4, 2, 5]
sorted_unique_nums = sort_and_deduplicate(nums)
print(sorted_unique_nums)  # 输出：[1, 2, 3, 4, 5, 6]

2、利用堆

def findKthLargest(nums, k):min_heap = [] #用来表示一个最小堆，堆通常通过列表实现for num in nums:if len(min_heap) < k:  # 检查堆的大小是否小于 kheapq.heappush(min_heap, num)else:if num > min_heap[0]:  # 如果堆的大小已经等于 kheapq.heapreplace(min_heap, num)return min_heap[0]  # 堆顶元素是第 K 大的元素

三、堆相关的知识科普

关于堆知识的总结：

关于堆知识的总结

堆是一种特殊的完全二叉树，满足堆序性质。
最小堆的堆顶是最小值，最大堆的堆顶是最大值。
堆的主要操作包括插入、弹出堆顶元素和堆化。
堆在优先队列、堆排序、查找第 K 大/小的元素等场景中非常有用。
在 Python 中，堆通过 heapq 模块实现，默认支持最小堆。

1. 堆的定义

堆是一种特殊的完全二叉树，满足以下两个条件：

完全二叉树：
- 堆是一棵完全二叉树，即每一层（除了最后一层）都被完全填满，并且所有节点都尽可能向左对齐。
- 这种结构使得堆可以用数组（列表）高效地表示，而不需要使用指针。
堆序性质：
- 堆中的每个节点都满足某种顺序关系，具体取决于堆的类型：
  - 最小堆（Min-Heap）：每个节点的值都小于或等于其子节点的值。
  - 最大堆（Max-Heap）：每个节点的值都大于或等于其子节点的值。

2. 堆的类型

堆主要有两种类型：

最小堆（Min-Heap）：
- 堆顶（根节点）是堆中最小的元素。
- 适用于需要快速访问最小值的场景，如优先队列。
最大堆（Max-Heap）：
- 堆顶（根节点）是堆中最大的元素。
- 适用于需要快速访问最大值的场景，如任务调度。

3. 堆的结构

堆通常用数组（列表）来表示，因为完全二叉树的结构使得数组可以高效地映射树的节点。对于一个数组 heap：

索引 i 的节点：
- 左子节点的索引是 2 * i + 1
- 右子节点的索引是 2 * i + 2
- 父节点的索引是 (i - 1) // 2

示例：最小堆 假设有一个最小堆 [1, 3, 2, 6, 5, 4]，其结构如下：

        1/   \3     2/ \   /6   5 4

4. 堆的操作

堆的主要操作包括：

插入元素：
- 将新元素添加到堆的末尾。
- 通过“上浮”操作调整堆的结构，确保父节点小于（最小堆）或大于（最大堆）子节点。
弹出堆顶元素：
- 移除并返回堆顶元素（最小堆的最小值或最大堆的最大值）。
- 将最后一个元素移到堆顶。
- 通过“下沉”操作调整堆的结构，确保父节点小于（最小堆）或大于（最大堆）子节点。
替换堆顶元素：
- 弹出堆顶元素，并将新元素插入堆中，同时保持堆的大小不变。
- 这是“上浮”和“下沉”操作的结合。
堆化：
- 将一个无序数组转换为一个有效的堆。
- 在 Python 中，使用 heapq.heapify() 实现。

6. 堆的应用

堆在算法和数据结构中有着广泛的应用，包括但不限于：

优先队列：
- 最小堆用于实现最小优先队列。
- 最大堆用于实现最大优先队列。
堆排序：
- 利用堆的性质对数组进行排序，时间复杂度为 O(n log n)。
查找第 K 大/小的元素：
- 使用最小堆或最大堆可以高效地找到数组中的第 K 大或第 K 小的元素。
中位数查找：
- 使用一个最大堆和一个最小堆可以动态维护数据流的中位数。
合并有序数组：
- 使用最小堆可以高效地合并多个有序数组。

7. Python 中的堆实现

Python 的 heapq 模块提供了对最小堆的支持。以下是一些常用操作：

Python复制

import heapq# 创建一个空堆
min_heap = []# 将一个列表转换为堆
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)# 向堆中添加元素
heapq.heappush(min_heap, 10)# 弹出堆顶元素
smallest = heapq.heappop(min_heap)# 替换堆顶元素
heapq.heapreplace(min_heap, 11)

算法题：数组中的第 K 个最大元素（中等难度）

一、题目给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。示例 1： 输入：nums [3,2,1,5,6,4], k 2 输出：…...

编程日记 2025/9/11 13:59:40

进行性核上性麻痹患者的生活护理指南

进行性核上性麻痹是一种神经系统退行性疾病，合理的生活护理能有效改善症状，提高生活质量。居家环境要安全。移除地面杂物，铺设防滑垫，安装扶手，降低跌倒风险。在浴室、厨房等湿滑区域要特别加强防护措施。建议在床边、…...

编程日记 2025/9/8 18:21:25

Python大战Java：AI时代的编程语言‘复仇者联盟‘能否换C位？

背景当Java程序员在咖啡机前念叨’Python凭什么抢我饭碗’时，AI实验室里的Python工程师正用5行代码召唤出神经网络——这场编程语言的’权力的游戏’，胜负可能比你想象的更魔幻！" 一、茶水间里的战争：Java和Python的相爱相…...

编程日记 2025/9/11 15:44:32

SpringBoot AI + PgVector向量库 + Openai Embedding模型

Spring Boot 项目引入下载仓库地址 <dependencyManagement><dependencies><dependency><groupId>org.springframework.ai</groupId><artifactId>spring-ai-bom</artifactId><version>${spring-ai.version}</version>&l…...

编程日记 2025/9/9 12:28:51

目标检测——数据处理

1. Mosaic 数据增强 Mosaic 数据增强步骤: (1). 选择四个图像： 从数据集中随机选择四张图像。这四张图像是用来组合成一个新图像的基础。 (2) 确定拼接位置： 设计一个新的画布(输入size的2倍)，在指定范围内找出一个随机点（如…...

编程日记 2025/9/7 18:56:08

数据集笔记：新加坡LTA MRT 车站出口、路灯等位置数据集

1 MRT 车站出口 data.gov.sg （geojson格式） 1.1 kml格式 data.gov.sg 2 路灯 data.govsg ——geojson data.gov.sg——kml 版本 3 道路摄像头数据集 data.gov.sg 4 自行车道网络 data.gov.sg 5 学校区域 data.gov.sg 6 自行车停车架&#xff…...

编程日记 2025/9/8 19:40:47

Highcharts 配置语法详解

Highcharts 配置语法详解引言 Highcharts 是一个功能强大的图表库，广泛应用于数据可视化领域。本文将详细介绍 Highcharts 的配置语法，帮助您快速上手并制作出精美、实用的图表。高级配置结构 Highcharts 的配置对象通常包含以下几部分&#xff1a…...

编程日记 2025/9/11 19:02:58

Python 项目安全实战：工具应用、规范制定、数据防护与架构加固

Python 项目安全实战：工具应用、规范制定、数据防护与架构加固本文聚焦 Python 项目安全，深入介绍安全工具如 Bandit、OWASP ZAP 的实战操作，涵盖对特定模块扫描及 Web 测试进阶应用。详细阐述团队如何制定并持续更新安全编码规范&#xff…...

编程日记 2025/9/10 20:24:36

linux ununtu通过nginx-1.6.2.tar.gz安装nginx并安装在自定义目录XXX下的步骤

Ubuntu 下通过源码安装 Nginx 1.6.2 到自定义目录 /home/aot/nginx 的步骤以下是将 Nginx 1.6.2 源码包离线安装到自定义目录的详细流程，包含依赖管理、编译配置和服务管理： 一、准备工作 1. 下载源码包和依赖（需联网环境准备）…...

编程日记 2025/9/10 13:52:51

《Python百练成仙》31-40章（不定时更新）

第卅一章函数结丹def开紫府罗酆山的鬼门关吞吐着猩红的变量阴风，每个风眼都涌动着作用域混乱的灵力乱流。叶军手握薛香遗留的丹田玉简，玉简表面浮现出残缺的函数符文： def 凝聚金丹(灵气):道基灵气 * 0.618print(金丹品质) # 作用域外变…...

编程日记 2025/9/8 4:54:09

Python--内置模块和开发规范（上）

1. 内置模块 1.1 JSON 模块核心功能序列化：Python 数据类型 → JSON 字符串 import json data [{"id": 1, "name": "武沛齐"}, {"id": 2, "name": "Alex"}] json_str json.dumps(data, ensure_a…...

编程日记 2025/9/9 8:07:20

使用DeepSeek实现自动化编程：类的自动生成

目录简述 1. 通过注释生成C类 1.1 模糊生成 1.2 把控细节，让结果更精准 1.3 让DeepSeek自动生成代码 2. 验证DeepSeek自动生成的代码 2.1 安装SQLite命令行工具 2.2 验证DeepSeek代码 3. 测试代码下载简述在现代软件开发中，自动化编程工具如…...

编程日记 2025/9/8 8:04:13

植物大战僵尸金铲铲版 v1.1.6（windows+安卓）

游戏简介《植物大战僵尸金铲铲版》是由“古见xzz”、“对不起贱笑了”、“是怪哉吖”等联合开发的民间魔改版本，融合了原版塔防玩法与《金铲铲之战》的自走棋元素，属于非官方同人作品。游戏特点合成升星机制：三个相同低星植物可合成更高…...

编程日记 2025/9/10 16:51:41

LeetCode 热题 100_寻找两个正序数组的中位数（68_4_困难_C++）(二分查找)（先合并再挑选中位数；划分数组（二分查找））

LeetCode 热题 100_寻找两个正序数组的中位数（68_4） 题目描述：输入输出样例：题解：解题思路：思路一（先合并再挑选中位数）：思路二（划分数组（二分查找…...

编程日记 2025/9/11 1:25:37

酒店管理系统(代码+数据库+LW)

摘要时代的发展带来了巨大的生活改变，很多事务从传统手工管理转变为自动管理。自动管理是利用科技的发展开发的新型管理系统，这类管理系统可以帮助人完成基本的繁琐的反复工作。酒店是出门的必需品，无论出差还是旅游都需要酒店的服务。由…...

编程日记 2025/9/9 0:13:00

关于C/C++的输入和输出

目录一、C语言中的scanf 有关scanf()的例子二、C语言中的printf 有关printf()的例子三、C中的cin、cout 四、字符的输入 1、cin.get() 2、cin.get() 3、cin.getline() 4、getline() 5、getchar() 五、string类型字符串长度 1、length() 2、size() 一、C语言中…...

编程日记 2025/9/11 0:05:29

袋鼠数据库工具 6.4 AI 版已上线

袋鼠数据库工具 6.4 AI 版已于 2025 年 2 月 26 日上线1。以下是该版本的一些新特性1： 地图支持：支持坐标定位并支持缩放动画；支持路线图，可在路线位置之间跳转；支持图层切换、标记和路线图图层切换；支持新…...

编程日记 2025/9/12 1:24:17

【AGI】DeepSeek开源周：The whale is making waves！

DeepSeek开源周：The whale is making waves！ 思维火花引言一、DeepSeek模型体系的技术演进1. 通用语言模型：DeepSeek-V3系列2. 推理优化模型：DeepSeek-R1系列3. 多模态模型：Janus系列二、开源周三大工具库的技术解析1…...

编程日记 2025/8/24 18:51:18

【无人机】无人机飞行日志下载及分析，飞行日志分析软件的使用

目录一、飞行日志下载 1.1 通过地面站下载 1.1.1 QGroundControl（QGC）地面站 1.1.2 Mission Planner 地面站 1.2 通过内存卡读卡器下载 1.3 通过数传模块下载（数传日志） 二、飞行日志分析 2.1 使用 Flight Review 分析 …...

编程日记 2025/9/11 8:07:27

【朝夕教育】《鸿蒙原生应用开发从零基础到多实战》003-TypeScript 中的类

标题详情作者简介愚公搬代码头衔华为云特约编辑，华为云云享专家，华为开发者专家，华为产品云测专家，CSDN博客专家，CSDN商业化专家，阿里云专家博主，阿里云签约作者，腾讯云优秀博主&…...

编程日记 2025/9/7 19:02:54

Java并发编程之可见性、原子性和有序性

引言 CPU缓存与内存产生的一致性问题（可见性） CPU时间片切换产生的原子性问题 CPU指令编译优化产生的有序性问题并发编程问题的根源 CPU、内存、I/O设备三者速度差异一直是核心矛盾三者速度差异可形象描述为：天上一天(CPU)，…...

编程日记 2025/9/10 0:42:40

99分巧克力

99分巧克力 ⭐️难度：中等 🌟考点：二分 2017省赛真题 📖 📚 import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc new Scanner(System.in);int n sc.nextInt();i…...

编程日记 2025/9/8 21:41:01

阿里重磅模型深夜开源；DeepSeek宣布开源DeepGEMM；微软开源多模态AI Agent基础模型Magma...|网易数智日报

阿里重磅模型深夜开源：表现超越Sora、Pika，消费级显卡就能跑 2月26日，25日深夜阿里云视频生成大模型万相2.1（Wan）正式宣布开源，此次开源采用Apache2.0协议，14B和1.3B两个参数规格的全部推理代码…...

编程日记 2025/9/10 8:37:53

目录 1. WPF属性系统1.1. CLR属性（CLR Properties）1.2. 相关属性（Related Properties）1.3. 附加属性（Attached Properties）1.4. 依赖属性（Dependency Properties）2. 依赖属性2.1. 定义2.2. 应用场景2.3. 理解2.3.1. 初识依赖属性2.3.2. 自定义依赖属性2.3.3. 使用依赖属…...

编程日记 2025/9/9 6:22:45

Python PDF文件拆分-详解

目录使用工具将PDF按页数拆分将PDF的每一页拆分为单独的文件将PDF按指定页数拆分根据页码范围拆分PDF 根据指定内容拆分PDF 将PDF的一页拆分为多页在日常生活中，我们常常会遇到大型的PDF文件，这些文件可能难以发送、管理和查阅。将PDF拆分成…...

编程日记 2025/9/8 1:43:13

ollama本地部署DeepSeek-R1大模型使用前端JS调用的详细流程

以下是关于如何在本地部署 DeepSeek-R1 大模型（通过 Ollama），并使用前端 JavaScript 调用其功能的详细流程。前提条件硬件要求： 建议至少 16GB RAM（运行较小模型如 1.5B 或 7B 参数版本），如果…...

编程日记 2025/9/8 20:37:11

Spring Cloud Alibaba与Spring Boot、Spring Cloud版本对应关系

一、前言在搭建SpringCloud项目环境架构的时候，需要选择SpringBoot和SpringCloud进行兼容的版本号，因此对于选择SpringBoot版本与SpringCloud版本的对应关系很重要，如果版本关系不对应，常见的会遇见项目启动不起来，怪…...

编程日记 2025/9/8 19:24:47

初识SQL

SQL 定义：SQL（Structured Query Language，结构化查询语言）是一种标准化的数据库操作语言，广泛用于关系数据库管理系统（RDBMS），如 MySQL、PostgreSQL 等。它支持数据的定义&#xff0…...

编程日记 2025/8/16 11:59:20

12_Pandas时序数据（上）

固定时间时间的表示固定时间是指一个时间点。固定时间是时序数据的基础，一个固定时间带有丰富的信息，如年份、周几、月份、季度等。 Python的官网库datetime支持创建和处理时间： datetime.now() # 当前时间 datetime(2025,2,26,12) # 指…...

编程日记 2025/9/7 16:09:20

当我删除word文件时无法删除，提示：操作无法完成，因为已在Microsoft Word中打开

现象： 查看电脑桌面下方的任务栏，明明已经关闭了WPS和WORD软件，但是打开word文档时还是提示： 解决方法步骤： 1、按一下键盘上的ctrl Shift Esc 键打开任务管理器 2、在进程中找到如下： 快速找到的方法…...

编程日记 2025/9/9 10:34:29

0x03 http协议和分层架构

HTTP协议简介 Hyper Text Transfer Protocol，超文本传输协议，规定了浏览器和服务器之间数据传输的规则 http协议基于TCP协议：面向连接，安全基于请求-响应模型：一次请求对应一次响应HTTP协议是无状态的协议&#xff…...

编程日记 2025/9/8 14:19:06

JavaScript系列03-异步编程全解析

本文介绍了异步相关的内容，包括： 回调函数与回调地狱Promise详解async/await语法Generator函数事件循环机制异步编程最佳实践 1、回调函数与回调地狱 JavaScript最初是为处理网页交互而设计的语言，异步编程是其核心特性之一。最早的异步编…...

编程日记 2025/9/9 17:54:17

深度解读 AMS1117：从电气参数到应用电路的全面剖析

在电子设备的电源管理领域，线性稳压器扮演着至关重要的角色，而 AMS1117 凭借其出色的性能和广泛的适用性，成为众多工程师的热门选择。本文将依据相关资料，对 AMS1117 的特性、应用、电气参数等方面进行详细解读。一、功能特性概…...

编程日记 2025/9/8 8:24:41

深入理解Tomcat与Web应用部署：C/S与B/S架构下的实践指南

在当今的互联网时代，Web应用的开发与部署是软件开发领域的重要组成部分。无论是传统的C/S架构，还是现代广泛应用的B/S架构，了解它们的优缺点以及如何高效部署Web应用是每个开发者都需要掌握的技能。本文将深入探讨C/S与B/S架构的区别&#xf…...

编程日记 2025/9/8 1:12:41

XML 编辑器：全面指南与最佳实践

XML 编辑器：全面指南与最佳实践引言 XML（可扩展标记语言）编辑器是处理XML文件的关键工具，对于开发人员、系统管理员以及任何需要处理XML数据的人来说至关重要。本文将全面介绍XML编辑器的概念、功能、选择标准以及最佳实践，旨在帮助读者了解如何选择和使用合适的XML编辑…...

编程日记 2025/9/11 13:16:47

Python实现GO鹅优化算法优化BP神经网络回归模型项目实战

说明：这是一个机器学习实战项目（附带数据代码文档视频讲解），如需数据代码文档视频讲解可以直接到文章最后关注获取。 1.项目背景传统BP神经网络的局限性：BP（Back Propagation）神经网络作为一种…...

编程日记 2025/9/6 13:31:58

如何配置虚拟机的IP上网

要配置虚拟机的IP地址以便上网，你可以按照以下步骤操作： 打开虚拟机软件，确保虚拟机的网络设置为“桥接模式”或“NAT模式”，这样虚拟机可以与物理网络连接。在虚拟机操作系统中，打开网络设置界面，一般在…...

编程日记 2025/9/9 13:35:52

【洛谷贪心算法题】P1094纪念品分组

该题运用贪心算法，核心思想是在每次分组时，尽可能让价格较小和较大的纪念品组合在一起，以达到最少分组的目的。【算法思路】输入处理：首先读取纪念品的数量n和价格上限w，然后依次读取每件纪念品的价格，…...

编程日记 2025/9/8 1:43:14

学习笔记08——ConcurrentHashMap实现原理及源码解析

1. 概述为什么需要ConcurrentHashMap？ 解决HashMap线程不安全问题：多线程put可能导致死循环（JDK7）、数据覆盖（JDK8） 优化HashTable性能：通过细粒度锁替代全局锁，提高并发度对比…...

编程日记 2025/8/30 10:02:43

redis slaveof 命令执行后为什么需要清库重新同步

在 Redis 中，执行 SLAVEOF（或 REPLICAOF）命令后，从节点需要清空现有数据并重新同步的主要原因如下： 1. 保证数据一致性核心目标：确保从节点的数据与主节点完全一致。问题场景： 如果从节点之前…...

编程日记 2025/9/9 17:54:45

6-1JVM的执行引擎处理

一、执行引擎的组成结构解释器（Interpreter） 逐条解释执行字节码指令，启动速度快但执行效率较低。适用于短生命周期或对启动时间敏感的场景，如调试环境。即时编译器（JIT Compiler） 通过动态…...

编程日记 2025/9/7 14:44:59

CMU15445(2023fall) Project #4 - Concurrency Control踩坑历程

把树木磨成月亮最亮时的样子， 就能让它更快地滚下山坡， 有时会比骑马还快。完整代码见： SnowLegend-star/CMU15445-2023fall: Having Conquered the Loftiest Peak, We Stand But a Step Away from Victory in This Stage. With unwavering…...

编程日记 2025/9/11 3:48:43

腿足机器人之十三-强化学习PPO算法

腿足机器人之十三-强化学习PPO算法腿足机器人位姿常用强化学习算法PPO算法核心原理PPO算法的创新设计PPO算法典型流程优势函数对于复杂地形适应性（如楼梯、碎石路），传统的腿足机器人采用基于模型的控制器，该方法依赖精确动力学建…...

编程日记 2025/9/11 9:50:53

ubuntu下r8125网卡重启丢失修复案例一则

刚装的一台服务器，ubuntu24.04，主板网卡是r8125，安装服务后会莫名其妙丢失驱动按照官网的方法下载最新8125驱动包： Realtek 然后卸载驱动 rmmod r8125 然后在驱动包里安装（幸好我之前装了build-essential&#x…...

编程日记 2025/9/7 18:03:10

设计一个“车速计算”SWC，通过Sender-Receiver端口输出车速信号。

1. 需求分析功能目标：根据车轮脉冲信号（轮速传感器输入）计算当前车速，并将结果通过Sender端口发送给其他SWC。输入：轮速脉冲数（如WheelPulse，类型uint32）。输出：车速（如VehicleSpeed，类型float32，单位km/h）。触发方式：周期性计算（例如每10ms执行一次）。 2.…...

编程日记 2025/9/11 20:01:45

DeepSeek 使用窍门与提示词写法指南

一、通用提示词技巧窍门分类技巧说明示例提示词明确需求用“角色任务要求”明确目标作为健身教练，为30岁上班族设计一周减脂计划，需包含饮食和15分钟居家训练结构化提问分步骤、分模块提问第一步：列出Python爬虫必备的5个库；第二…...

编程日记 2025/9/9 22:33:19

MySQL零基础教程12—聚合查询（聚合函数）

背景有时候我们需要汇总一些数据，比如查询一个班级的平均分数，这个时候我们需要的是把分数汇总，然后计算出一个平均值进行返回，并不需要返回某一列的值，针对这种场景，mysql中提供了一些聚合函数帮助快速完…...

编程日记 2025/9/8 21:54:34

JMeter 引入 JAR 包的几种方法

JMeter 支持加载外部 JAR 文件，用于： 扩展 JMeter 功能使用 Java 代码（BeanShell / JSR223）连接数据库 / 解析 Excel / 读取 CSV 📌 1. JMeter 引入 JAR 包的方式 ✅ 方式 1：将 JAR 放入 lib/ 或 lib/ext…...

编程日记 2025/9/7 18:01:00