輸入整數(shù)數(shù)組 arr ，找出其中最小的 k 個(gè)數(shù)。例如，輸入4、5、1、6、2、7、3、8這8個(gè)數(shù)字，則最小的4個(gè)數(shù)字是1、2、3、4。

示例

• 輸入：arr = [3,2,1], k = 2

• 輸出：[1,2] 或者 [2,1]

限制

• 0 <= k <= arr.length <= 10000

• 0 <= arr[i] <= 10000

方法：數(shù)組排序

對(duì)目標(biāo)數(shù)組進(jìn)行從小到大排序，然后取前 k 個(gè)數(shù)即可。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(nlogn)，其中 n 是數(shù)組 arr 的長(zhǎng)度。算法的時(shí)間復(fù)雜度即排序的時(shí)間復(fù)雜度。

• 空間復(fù)雜度：O(logn)，排序所需額外的空間復(fù)雜度為 O(logn)。

方法：大根堆

創(chuàng)建一個(gè)大根堆，把前 k 個(gè)值插入到堆中，從 K+1 開(kāi)始如果當(dāng)前值比 堆頂?shù)闹敌?，就彈出，把?dāng)前值放入到堆中，最后將堆以數(shù)組的形式返回。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(nlogk)，其中 n 是數(shù)組 arr 的長(zhǎng)度。由于大根堆實(shí)時(shí)維護(hù)前 k 小值，所以插入刪除都是 O(logk) 的時(shí)間復(fù)雜度，最壞情況下數(shù)組里 n個(gè)數(shù)都會(huì)插入，所以一共需要 O(nlogk) 的時(shí)間復(fù)雜度。

• 空間復(fù)雜度：O(k)，因?yàn)榇蟾牙镒疃?k 個(gè)數(shù)。

方法：快速排序

該方法出自 “K神”的題解，快速排序算法有兩個(gè)核心點(diǎn)，分別為 “哨兵劃分” 和 “遞歸” 。

• 哨兵劃分操作： 以數(shù)組某個(gè)元素（一般選取首元素）為 基準(zhǔn)數(shù) ，將所有小于基準(zhǔn)數(shù)的元素移動(dòng)至其左邊，大于基準(zhǔn)數(shù)的元素移動(dòng)至其右邊。

• 遞歸： 對(duì)左子數(shù)組 和右子數(shù)組 遞歸執(zhí)行 哨兵劃分，直至子數(shù)組長(zhǎng)度為 1 時(shí)終止遞歸，即可完成對(duì)整個(gè)數(shù)組的排序。

代碼如下：

復(fù)雜度分析

• 時(shí)間復(fù)雜度： O(NlogN) 。

• 空間復(fù)雜度： O(N)。

END

業(yè)精于勤荒于嬉，行成于思?xì)в陔S，贈(zèng)友人。

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號(hào)“javaAnswer”，全部都是干貨。