Leetcode 剑指 Offer II 076.数组中的第 K 个最大元素

2024-05-06 04:44

本文主要是介绍Leetcode 剑指 Offer II 076.数组中的第 K 个最大元素,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目难度: 中等

原题链接

今天继续更新 Leetcode 的剑指 Offer(专项突击版)系列, 大家在公众号 算法精选 里回复 剑指offer2 就能看到该系列当前连载的所有文章了, 记得关注哦~

题目描述

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

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

示例 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 <= 10^4
  • -10^4 <= nums[i] <= 10^4

题目思考

  1. 可以使用什么数据结构?

解决方案

思路
  • 分析题目, 一个很容易想到的思路就是对数组从大到小排序, 然后第 k 个元素即为所求
  • 不过这种方法需要对所有数字进行排序, 题目只要求第 k 大的, 有没有更优的方法呢?
  • 第 k 问题通常都可以尝试用堆/优先队列来解决, 这道题也不例外
  • 如果我们只存最大的 k 个数字到一个最小堆中, 那么只需返回堆顶即可, 无需对所有数字排序
  • 这就引出了下面的思路:
    • 维护一个最小堆
    • 遍历数组, 将当前数字直接加入堆中
    • 加入后如果堆中元素超过了 k, 就把堆顶弹出
    • 由于是最小堆, 上述操作保证了堆中元素正是当前最大的 k 个数字, 更小的都被弹出去了
    • 此时堆顶就是第 k 大的元素, 直接返回堆顶即可
  • 另外这道题目还可以使用类似快速排序以及自定义堆的思路, 我之前的这篇文章(剑指 Offer 40. 最小的 k 个数)就包含了解决这类问题的 4 种方案和代码细节, 只是那道题稍微不同, 是求最小 k, 需要使用最大堆
  • 大家感兴趣的话可以尝试参考那些思路来解决这道题, 这样举一反三可能会有新的收获~
  • 下面代码中有详细的注释, 方便大家理解
复杂度
  • 时间复杂度 O(NlogK): 遍历整个数组是 O(N), 每次添加数字都是操作最多 K 个元素的最小堆, 这部分是 O(logK), 所以整体就是 O(NlogK)
  • 空间复杂度 O(K): 最小堆存储最多 K 个元素
代码
class Solution:def findKthLargest(self, nums: List[int], k: int) -> int:# 最小堆pq = []for x in nums:# 将当前值加入最小堆heapq.heappush(pq, x)if len(pq) > k:# 最小堆的元素数目超过了k, 弹出堆顶最小值heapq.heappop(pq)# 此时堆中存储的就是整个数组的最大k个数, 而堆顶就是第k大的return pq[0]

大家可以在下面这些地方找到我~😊

我的 GitHub

我的 Leetcode

我的 CSDN

我的知乎专栏

我的头条号

我的牛客网博客

我的公众号: 算法精选, 欢迎大家扫码关注~😊

算法精选 - 微信扫一扫关注我

这篇关于Leetcode 剑指 Offer II 076.数组中的第 K 个最大元素的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/963452

相关文章

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

C# 比较两个list 之间元素差异的常用方法

《C#比较两个list之间元素差异的常用方法》:本文主要介绍C#比较两个list之间元素差异,本文通过实例代码给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1. 使用Except方法2. 使用Except的逆操作3. 使用LINQ的Join,GroupJoin

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

python3如何找到字典的下标index、获取list中指定元素的位置索引

《python3如何找到字典的下标index、获取list中指定元素的位置索引》:本文主要介绍python3如何找到字典的下标index、获取list中指定元素的位置索引问题,具有很好的参考价值,... 目录enumerate()找到字典的下标 index获取list中指定元素的位置索引总结enumerat

CSS实现元素撑满剩余空间的五种方法

《CSS实现元素撑满剩余空间的五种方法》在日常开发中,我们经常需要让某个元素占据容器的剩余空间,本文将介绍5种不同的方法来实现这个需求,并分析各种方法的优缺点,感兴趣的朋友一起看看吧... css实现元素撑满剩余空间的5种方法 在日常开发中,我们经常需要让某个元素占据容器的剩余空间。这是一个常见的布局需求

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA

JAVA数组中五种常见排序方法整理汇总

《JAVA数组中五种常见排序方法整理汇总》本文给大家分享五种常用的Java数组排序方法整理,每种方法结合示例代码给大家介绍的非常详细,感兴趣的朋友跟随小编一起看看吧... 目录前言:法一:Arrays.sort()法二:冒泡排序法三:选择排序法四:反转排序法五:直接插入排序前言:几种常用的Java数组排序

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a