牛客網 面試筆試? ?TOP101 ? ?| ? ? LeetCode 面試題 17.14. ?最小K個數

1. 題目

描述

給定一個長度為 n 的可能有重復值的數組，找出其中不去重的最小的 k 個數。例如數組元素是4,5,1,6,2,7,3,8這8個數字，則最小的4個數字是1,2,3,4(任意順序皆可)。

數據范圍：0≤k,n≤10000，數組中每個數的大小0≤val≤1000

要求：空間復雜度 O(n)，時間復雜度 O(nlogn)

示例1

輸入：

[4,5,1,6,2,7,3,8],4

返回值：

[1,2,3,4]

說明：

返回最小的4個數即可，返回[1,3,2,4]也可以 ? ? ? ?

示例2

輸入：

[1],0

返回值：

[ ]

示例3

輸入：

[0,1,2,1,2],3

返回值：

[0,1,1]

2. 解題思路

最小的K個數的求解問題是典型的Top K問題，一般通過堆來完成。先來看看什么是堆：

堆" 是一個在計算機科學中經常使用的術語，它通常指的是一種特殊的樹形數據結構——二叉堆（binary heap）。二叉堆通常滿足堆屬性（heap property），即父節點的值總是大于或等于（或小于或等于，取決于堆的類型）其子節點的值。

堆是一種完全二叉樹結構，并滿足以下性質之一：

• 最大堆（Max-Heap）：每個父節點的值大于或等于其子節點的值。

• 最小堆（Min-Heap）：每個父節點的值小于或等于其子節點的值。

核心特性

1. 完全二叉樹：

   除了最后一層，其他層節點全部填滿，且最后一層節點盡可能靠左排列。

2. 高效操作：

   插入和刪除操作的時間復雜度為 O(log n)，建堆時間復雜度為 O(n)。

堆的存儲方式

• 數組實現（最常用）：

  • 父節點索引為 i，則左子節點為 2i+1，右子節點為 2i+2。

  • 子節點索引為 i，則父節點為 (i-1)//2。

• 示例

  （數組表示的堆）：

  <span style="background-color:#f8f8f8 !important">數組：[9, 5, 3, 2, 4, 1]
  對應完全二叉樹：9/   \5     3/ \   /2  4 1

---

堆的應用場景

優先隊列：任務調度、Dijkstra 算法。

• 堆排序：時間復雜度 O(n log n)，原地排序但不穩定。

• Top K 問題：快速找到數據流中最大/最小的 K 個元素。

• 合并有序序列：如合并 K 個有序鏈表。

堆（Heap）是一種特殊的樹形數據結構，通常以完全二叉樹的形式實現，具有以下核心特性：

---

常見誤區

1. 堆與內存堆：

   數據結構中的“堆”與程序內存管理中的“堆”（Heap Memory）完全不同。

2. 堆的有序性：

   堆僅保證根節點是極值，子樹之間不一定有序。

如果文字描述的不太清楚，你可以參考視頻的詳細講解。

• Python編碼：Python數據結構LeetCode筆試面試算法_嗶哩嗶哩_bilibiliPython數據結構LeetCode筆試面試算法,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1372869

• Java編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367923

• Golang編碼：LeetCode數據結構筆試面試算法-Go語言版_嗶哩嗶哩_bilibiliLeetCode數據結構筆試面試算法-Go語言版,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1364949

3. 編碼實現

核心代碼如下：

/*** 代碼中的類名、方法名、參數名已經指定，請勿修改，直接返回方法規定的值即可*** @param input int整型一維數組* @param k int整型* @return int整型一維數組*/
func GetLeastNumbers_Solution(input []int, k int) []int {// write code hereres := make([]int, 0)if k == 0 || len(input) < k {return res}//1.定義一個大頂堆（最大元素在最上面）h := make(MyHeap, 0, k)heap.Init(&h)//2.先將k個元素加入堆for i := 0; i < k; i++ {heap.Push(&h, input[i])}//3.如果當前元素小于堆頂的元素（待加入的元素比堆中的小）則將堆中的最大元素彈出，新元素入堆//彈出的作用：保證堆中只存儲最小的k個數據for i := k; i < len(input); i++ {if input[i] < h[0] {heap.Pop(&h)heap.Push(&h, input[i])}}//4.堆中的元素彈出，存儲到數組中返回for h.Len() > 0 {res = append(res, heap.Pop(&h).(int))}return res
}

具體完整代碼你可以參考下面視頻的詳細講解。

• Python編碼：Python數據結構LeetCode筆試面試算法_嗶哩嗶哩_bilibiliPython數據結構LeetCode筆試面試算法,bilibili課堂,嗶哩嗶哩課堂,嗶哩嗶哩,Bilibili,B站,彈幕https://www.bilibili.com/cheese/play/ep1372869

• Java編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1367923

• Golang編碼：嗶哩嗶哩_bilibilihttps://www.bilibili.com/cheese/play/ep1364949

4.小結

最小的K個數可以通過大頂堆完成，具體操作步驟為：

1. 定義一個大頂堆，堆的大小為 K；

2. 堆中存儲最小的K個數；

3. 先從數組中取出 K 個元素加入堆；

4. 再從數組中取出其他元素，如果該元素小于堆頂的元素，從堆中彈出元素，將該元素加入堆；

5. 數組中的元素取完，堆中的數據就是最小的K個數。

《數據結構與算法》深度精講課程正式上線啦！7 大核心算法模塊全解析：

? ? ? 鏈表

? ? ? 二叉樹

? ? ? 二分查找、排序

? ? ? 堆、棧、隊列

? ? ? 回溯算法

? ? ? 哈希算法

? ? ? 動態規劃

無論你是備戰筆試面試、提升代碼效率，還是突破技術瓶頸，這套課程都將為你構建扎實的算法思維底座。🔥立即加入學習打卡，與千名開發者共同進階！

• Python編碼實現：嗶哩嗶哩_bilibilihttps://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

對于數據結構與算法，我們總結了一套【可視化+圖解】方法，依據此方法來解決相關問題，算法變得易于理解，寫出來的代碼可讀性高也不容易出錯。具體也可以參考視頻詳細講解。

今日佳句：千磨萬擊還堅勁，任爾東西南北風。