一道非常典型的top N 的題目绪杏。
面試題40. 最小的k個(gè)數(shù)
題目描述很簡(jiǎn)單，輸出數(shù)組里面最小的K個(gè)數(shù)。
一般來說正常思路就是對(duì)數(shù)組進(jìn)行排序劣像，然后輸出最小的K個(gè)數(shù)。不過其實(shí)仔細(xì)想想其實(shí)可以用堆來做的摧玫。建個(gè)大小為k的大頂堆耳奕。堆數(shù)組里面的數(shù)進(jìn)入堆，如果堆頂大于數(shù)組的數(shù)诬像，則去掉堆頂數(shù)屋群，加入數(shù)組內(nèi)數(shù)字。
public int[] getLeastNumbers(int[] arr, int k) {
/**
*
* 功能描述:輸入整數(shù)數(shù)組 arr 坏挠，找出其中最小的 k 個(gè)數(shù)芍躏。例如，輸入4降狠、5纸肉、1、6喊熟、2柏肪、7、3芥牌、8這8個(gè)數(shù)字烦味，則最小的4個(gè)數(shù)字是1、2壁拉、3谬俄、4。
*
*
* @param: [arr, k]
* @return: int[]
* @auther: smallfish
* @date: 2020-03-20 10:59
*/
if (k == 0) {
return new int[0];
}
int[] result = new int[k];
//建大小為k的大頂堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k, (o1, o2) -> o2 - o1);
//填滿大頂堆
for (int i = 0; i < k; i++) {
priorityQueue.add(arr[i]);
}
//堆滿后弃理，如果堆頂大于數(shù)組的數(shù)溃论，則去掉堆頂數(shù)，加入數(shù)組內(nèi)數(shù)字痘昌。
for (int i = k; i < arr.length; i++) {
if (arr[i] < priorityQueue.peek()) {
priorityQueue.remove();
priorityQueue.add(arr[i]);
}
}
//輸出結(jié)果到result中
int start = 0;
while (priorityQueue.size() > 0) {
result[start++] = priorityQueue.remove();
}
return result;
}
