?從海量數(shù)字中尋找最大/小的 k 個，這類問題我們稱為 TopK 問題谱仪。
通常使用數(shù)據(jù)結(jié)構(gòu)-最大/小堆來解決
- 求前 k 大玻熙，用最小堆，即堆頂元素為堆中最小值疯攒。
- 求前 k 小嗦随，用最大堆，即堆頂元素為堆中最大值敬尺。
如前k大的值, 傳入列表 list=[12, 39, 3, 72, 56, 81, 15, 9, 103] 和 k=3, 輸出 [103, 81, 72]枚尼。
如前k小的值, 傳入列表 list=[12, 39, 3, 72, 56, 81, 15, 9, 103] 和 k=3, 輸出 [3, 9, 12]。
前K大值
思路：
迭代列表元素：
- 1.先放入元素前 k 個建立一個最小堆砂吞；
- 2.當前元素x若大于堆頂元素：移除堆頂元素并入隊x姑原；
- 3.最后獲取 最小堆 中的值，即為 topK4Max呜舒。
JAVA參考代碼
public static int[] topK4Max(int[] nums, int k) {
?
// 優(yōu)先隊列锭汛、從小到大 (默認也是自然排序)
Queue<Integer> minHeap = new PriorityQueue<>(Comparator.naturalOrder());
// 建立最小堆
for (int i = 0, len = nums.length; i < len; i++) {
if (minHeap.size() < k) {
minHeap.offer(nums[i]); // 入隊
continue;
}
if (nums[i] > minHeap.peek()) { // 取隊首元素比較，不移除
minHeap.poll(); // 取隊首元素袭蝗，并移除
minHeap.offer(nums[i]);
}
}
// 遍歷隊列
List<Integer> list = new ArrayList<>();
Iterator<Integer> iterator = minHeap.iterator();
while (iterator.hasNext()){
list.add(iterator.next());
}
// 從大到小排序
Collections.sort(list, (o1, o2) -> o1 < o2 ? 1 : o1 == o2 ? 0 : -1);
// 轉(zhuǎn)換成數(shù)組
return list.stream().mapToInt(Integer::valueOf).toArray();
?
}
前K小值
思路：
迭代列表元素：
- 1.先放入元素前 k 個建立一個最大堆唤殴；
- 2.當前元素x若小于堆頂元素：移除堆頂元素并入隊x；
- 3.最后獲取 最大堆 中的值到腥，即為 topK4Min朵逝。
JAVA參考代碼
public static int[] topK4Min(int[] nums, int k) {
?
// 優(yōu)先隊列、從大到小排序
Queue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
// 建立最大堆
for (int i = 0, len = nums.length; i < len; i++) {
if (maxHeap.size() < k) {
maxHeap.offer(nums[i]); // 入隊
continue;
}
if (nums[i] < maxHeap.peek()) { // 取隊首元素比較乡范，不移除
maxHeap.poll(); // 取隊首元素配名，并移除
maxHeap.offer(nums[i]);
}
}
// 遍歷隊列
List<Integer> list = new ArrayList<>();
Iterator<Integer> iterator = maxHeap.iterator();
while (iterator.hasNext()){
list.add(iterator.next());
}
// 從小到大排序
Collections.sort(list);
// 轉(zhuǎn)換成數(shù)組
return list.stream().mapToInt(Integer::valueOf).toArray();
}
測試代碼
public static void main(String[] args) {
int[] nums = new int[]{12, 39, 3, 72, 56, 81, 15, 9, 103};
?
int[] maxK = topK4Max(nums, 3);
System.out.println(JSON.toJSONString(maxK));
?
int[] minK = topK4Min(nums, 3);
System.out.println(JSON.toJSONString(minK));
}
