厦门翔安区建设局网站网站开发实战答案

牛客网 面试笔试  TOP101    |     LeetCode 215. 数组中的第K个最大元素

1. 题目

描述

有一个整数数组，请你找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

数据范围：0≤n≤105， 1≤K≤n，数组中每个元素满足 0 ≤val≤109

示例1

输入：

[1,3,5,2,2],5,3

返回值：

2

示例2

输入：

[10,10,9,9,8,7,5,6,4,3,4,2],12,3

返回值：

9

说明：

去重后的第3大是8，但本题要求包含重复的元素，不用去重，所以输出9        

2. 解题思路

本题求解的是数组中的第K个最大的元素，还是属于Top K问题，因此可以通过堆来实现。堆相关知识可以参考《可视化图解算法50：最小的K个数》，具体思路如下：

如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1372870

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367924

• Golang版本：哔哩哔哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364950

3. 编码实现

核心代码如下：

/*** 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可*** @param a int整型一维数组* @param n int整型* @param K int整型* @return int整型*/
func findKth(a []int, n int, K int) int {// write code here// 1. 构建一个小顶堆，存储最大的k个数据，最后返回 top对应的数据即可h := make(MyHeap, 0)heap.Init(&h)// 2. 将前k个元素入堆for i := 0; i < K; i++ {heap.Push(&h, a[i])}// 3. 如果待加入堆的元素 大于堆顶的数据，首先将堆顶元素出堆，再将新元素入堆for i := K; i < len(a); i++ {if a[i] > h[0] {heap.Pop(&h)heap.Push(&h, a[i])}}// 4. 返回堆顶元素return h[0]
}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1372870

• Java版本：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1367924

• Golang版本：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ep1364950

4.小结

本题还是典型的Top K问题，可以通过堆来实现。具体操作步骤为：

1. 定义一个小顶堆，堆的大小为 K；

2. 堆中存储最大的K个数；

3. 先从数组中取出 K 个元素加入堆；

4. 再从数组中取出其他元素，如果该元素大于堆顶的元素，从堆中弹出元素，将该元素加入堆；

5. 数组中的元素取完，堆顶的数据就是第k大的数。

《数据结构与算法》深度精讲课程正式上线啦！7 大核心算法模块全解析：

  ✅   链表

  ✅   二叉树

  ✅   二分查找、排序

  ✅   堆、栈、队列

  ✅   回溯算法

  ✅   哈希算法

  ✅   动态规划

无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：Python数据结构LeetCode笔试面试算法_哔哩哔哩_bilibiliPython数据结构LeetCode笔试面试算法,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：LeetCode数据结构笔试面试算法-Java版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Java版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：LeetCode数据结构笔试面试算法-Go语言版_哔哩哔哩_bilibiliLeetCode数据结构笔试面试算法-Go语言版,bilibili课堂,哔哩哔哩课堂,哔哩哔哩,Bilibili,B站,弹幕https://www.bilibili.com/cheese/play/ss63997

对于数据结构与算法，我们总结了一套【可视化+图解】方法，依据此方法来解决相关问题，算法变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。

今日佳句：穷且益坚，不坠青云之志。