牛客網 面試筆試? 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版本：嗶哩嗶哩_bilibili
https://www.bilibili.com/cheese/play/ep1372870 -
Java版本：LeetCode數據結構筆試面試算法-Java版_嗶哩嗶哩_bilibiliLeetCode數據結構筆試面試算法-Java版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕
https://www.bilibili.com/cheese/play/ep1367924 -
Golang版本：嗶哩嗶哩_bilibili
https://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問題，可以通過堆來實現。具體操作步驟為：
-
定義一個小頂堆，堆的大小為 K；
-
堆中存儲最大的K個數；
-
先從數組中取出 K 個元素加入堆；
-
再從數組中取出其他元素，如果該元素大于堆頂的元素，從堆中彈出元素，將該元素加入堆；
-
數組中的元素取完，堆頂的數據就是第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
對于數據結構與算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。
今日佳句：窮且益堅，不墜青云之志。
