LeetCode 补充题 208. 最大的 K 个数
题目描述
:::fold-green 相关原题
LeetCode 原题： ✅ LCR 159. 库存管理 III
LeetCode 原题选取最小的 k 个数；本文改为选取最大的 k 个数，重复值仍按出现次数保留。
:::
给定整数数组
arr和整数k，返回其中最大的k个数，结果顺序不限，重复值按出现次数保留。
示例 1：
输入：
arr = [3,1,5,2], k = 2
输出：[3,5]
提示：
0 <= k <= arr.length-
k = 0时返回空数组。
题意分析
只需要保留最大的 k 次出现，不必给全部元素排序。维护这 k 个候选中的最小值，才能在新数到来时快速判断它是否值得替换当前最弱候选。
解法：大小为 k 的小顶堆
核心思路
[!blue]
堆中始终保留目前见过的最大 k 个数，堆顶必须是其中最小的一个，因为它是最先应该被淘汰的候选。这就是求“最大 k 个数”反而使用小顶堆的原因。
未满 k 个时直接加入；已满时，新值不大于堆顶就不能改善结果，否则删除堆顶并加入新值。每次只改变一个候选，其他保留值仍优于已丢弃的值。
重复值按不同出现保留，不做集合去重。k 为 0 时直接返回空数组，避免读取空堆。
解题步骤
- k=0 时直接返回空数组，否则创建小顶堆。
- 堆未满 k 个时直接插入当前值。
- 堆已满时，只在当前值大于堆顶的情况下删除堆顶并插入当前值。
- 遍历结束返回堆中全部元素，输出无需再排序。
代码实现
class Solution {
public int[] getLargestNumbers(int[] arr, int k) {
int[] res = new int[k];
if (k == 0) {
return res;
}
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> Integer.compare(a, b));
for (int x : arr) {
if (heap.size() < k) {
heap.offer(x);
} else if (x > heap.peek()) {
heap.poll();
heap.offer(x);
}
}
for (int i = 0; i < k; i++) {
res[i] = heap.poll();
}
return res;
}
}
import "container/heap"
type minHeap []int
func (h minHeap) Len() int {
return len(h)
}
func (h minHeap) Less(i, j int) bool {
return h[i] < h[j]
}
func (h minHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *minHeap) Push(x any) {
*h = append(*h, x.(int))
}
func (h *minHeap) Pop() any {
old := *h
n := len(old)
v := old[n-1]
*h = old[:n-1]
return v
}
func getLargestNumbers(arr []int, k int) []int {
if k == 0 {
return []int{}
}
h := &minHeap{}
for _, x := range arr {
if h.Len() < k {
heap.Push(h, x)
} else if x > (*h)[0] {
heap.Pop(h)
heap.Push(h, x)
}
}
return []int(*h)
}
复杂度分析
- 时间复杂度：$O(n\log(k+1))$。
- 空间复杂度：额外空间 $O(k)$。
关键点总结
[!green]
维护大小至多为 k 的小顶堆，堆顶是当前最弱候选；新值大于堆顶时替换，从而始终保留最大的 k 次出现。
易错点总结
[!yellow]
- 这里使用小顶堆，堆顶代表已保留候选中最小的一项。
- 重复值按出现次数保留，不能用集合去重。
- k=0 时不能访问堆顶；结果顺序不限，Go 直接返回堆数组即可。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 剑指 Offer 40. 最小的k个数 | 简单 | 都可维护容量为 k 的候选堆；该题选最小的 k 个数、使用大顶堆，本题选最大的 k 个数、使用小顶堆，重复值均按次数保留。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！