leetcode hot100【LeetCode 215.数组中的第K个最大元素】java实现

ops/2024/11/27 13:15:52/

LeetCode 215.数组中的第K个最大元素

题目描述

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

请注意,要求排名是从大到小的,因此第 k 个最大元素是排序后的第 k 个元素。你需要设计一个高效的算法来解决这个问题。

示例 1:

输入:nums = [3,2,1,5,6,4], k = 2
输出:5
解释:数组中第二大的元素是 5

示例 2:

输入:nums = [3,2,3,1,2,4,5,5,6], k = 4
输出:4
解释:数组中第四大的元素是 4

Java 实现代码

java">class Solution {public int findKthLargest(int[] nums, int k) {// 使用最小堆来找第k大的元素PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);for (int num : nums) {minHeap.offer(num);if (minHeap.size() > k) {minHeap.poll(); // 维护堆的大小为k,去除堆中最小的元素}}return minHeap.peek(); // 最小堆的根就是第k大的元素}
}

解题思路

  1. 最小堆方法: 我们可以利用最小堆(PriorityQueue)来实现。堆是一个完全二叉树,可以在 O(logn) 时间内进行插入和删除操作。

    • 将数组中的前 k 个元素插入到最小堆中。
    • 如果当前堆中元素个数大于k,则吐出。
    • 最后,堆顶的元素就是第 k 大的元素。

    这种方法的时间复杂度是 O(n log k),其中 n 是数组的大小,k 是需要找到的第 k 大元素。

  2. 快速选择法: 另一种方法是使用快速排序的思想,即快速选择(Quickselect)。通过对数组进行划分,选择性地进入有可能包含第 k
    大元素的子数组。这个方法的平均时间复杂度是 O(n)

复杂度分析

  • 时间复杂度: 使用最小堆方法时,插入一个元素的时间复杂度是 O(log k),所以对于数组中 n 个元素,总的时间复杂度是 O(n log k)
  • 空间复杂度: O(k),因为堆中最多存储 k 个元素。

举例说明执行过程

假设有数组 nums = [3,2,1,5,6,4],我们要求第 2 大的元素。

  1. 初始数组:[3,2,1,5,6,4]k = 2
  2. 创建一个大小为 2 的最小堆:
    • 插入 3,堆为 [3]
    • 插入 2,堆为 [2, 3](因为堆是最小堆,所以自动调整)
    • 插入 1,堆为 [1, 3](删除最小元素 2
    • 插入 5,堆为 [3, 5](删除最小元素 1
    • 插入 6,堆为 [5, 6](删除最小元素 3
    • 插入 4,堆为 [5, 6](删除最小元素 4
  3. 最终堆中元素为 [5, 6],堆顶为 5,即第 2 大元素。

http://www.ppmy.cn/ops/137090.html

相关文章

Java基础.数组排序(冒泡排序和选择排序)数组与遍历

目录 排序 冒泡排序 优化的冒泡排序 选择排序 遍历 一、概念解释 二、目的和意义 数据处理 数据展示 数组基础 数组的定义 如何使用数组 数组初始化 数组长度 案例 案例1&#xff1a;计算班级平均分 案例2&#xff1a;计算班级平均分 案例3&#xff1a;记录运动成…

Redis 可观测最佳实践

Redis 介绍 Redis 是一个开源的高性能键值对&#xff08;key-value&#xff09;数据库。它通常用作数据库、缓存和消息代理。Redis 支持多种类型的数据结构&#xff0c;Redis 通常用于需要快速访问的场景&#xff0c;如会话缓存、全页缓存、排行榜、实时分析等。由于其高性能和…

自由学习记录(25)

只要有修改&#xff0c;子表就不用元表的参数了&#xff0c;用自己的参数&#xff08;只不过和元表里的那个同名&#xff09; 子表用__index“继承”了父表的值&#xff0c;此时子表仍然是空表 一定是创建这样一个同名的变量在原本空空的子表里&#xff0c; 传参要传具体的变…

STM32C011开发(2)----nBOOT_SEL设置

STM32C011开发----2.nBOOT_SEL设置 概述硬件准备视频教学样品申请源码下载参考程序自举模式BOOT0设置配置 nBOOT_SEL生成STM32CUBEMX串口配置LED配置堆栈设置串口重定向主循环演示 概述 STM32CubeProgrammer (STM32CubeProg) 是一款用于编程STM32产品的全功能多操作系统软件工…

mac maven编译出现问题

背景 进行maven install 命令&#xff0c;报错&#xff1a; [ERROR] COMPILATION ERROR : [INFO] ------------------------------------------------------------- [ERROR] No compiler is provided in this environment. Perhaps you are running on a JRE rather than a J…

【leetcode】动态规划

31. 873. 最长的斐波那契子序列的长度 题目&#xff1a; 如果序列 X_1, X_2, ..., X_n 满足下列条件&#xff0c;就说它是 斐波那契式 的&#xff1a; n > 3对于所有 i 2 < n&#xff0c;都有 X_i X_{i1} X_{i2} 给定一个严格递增的正整数数组形成序列 arr &#xff0…

Linux下通过DRM操作屏幕,发生行对齐 (stride)问题

前言 Linux下使用LVGL操作屏幕&#xff0c;屏幕尺寸是[280*1424]&#xff0c;不管如何设置LVGL的参数&#xff0c;屏幕的显示均为花屏&#xff0c;能看到有图像显示&#xff0c;但是图像是行错乱的。 ubuntu桌面系统显示正常 打印DRM看输出 drm: 280x1424 (0mm X 0mm) pixel …

OpenTK 实现三维空间模型仿真详解

文章目录 一、创建渲染窗口与初始化 OpenGL二、三维模型加载三、渲染管线搭建四、模型渲染与变换五、交互与事件处理一、创建渲染窗口与初始化 OpenGL 继承 GameWindow:   构建自定义类使其继承自 GameWindow,该类内部封装了诸多窗口管理以及渲染循环逻辑,为后续渲染工作…