LeetCode 面试题 17.14. 最小K个数

约 6 分钟
文章信息 12 个分类 6 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 字节跳动 美团 快手 腾讯 百度 网易 程序员面试金典（第 6 版）
标签
数组 排序 堆（优先队列） 分治 Top N 问题 快速选择
目录

题目描述

✅ 面试题 17.14. 最小 K 个数

image-20250420083518893

image-20230311221837863

题意分析

输入一个整数数组和一个整数 $k$，要求返回其中数值最小的 $k$ 个数，返回的这 $k$ 个数之间不要求任何顺序。

注意题目问的是「最小的这一批数」，而不是「第 $k$ 小的那一个数」，所以答案是一个长度为 $k$ 的数组，不是一个标量。

有两个约束信号值得留意。其一，$k$ 可以取到 $0$，此时合法答案是空数组，任何「先取一个元素再比较」的写法都会在这里出问题。其二，$k$ 也可以取到数组长度本身，此时整个数组都是答案。数组中允许出现重复值，重复值各自独立计数，例如 $[2, 2, 2]$ 取 $k = 2$ 时答案是两个 $2$。

「不要求顺序」这四个字是本题最重要的约束信号：它说明我们并不需要知道这 $k$ 个数各自的名次，只需要知道它们「属于最小的一批」这个集合归属关系。凡是题目没有要求的信息，都是可以省掉的计算量。

解法：大小为 K 的最大堆

核心思路

全量排序能取到前 k 个数，但它计算了所有元素的完整次序，时间是 O(n log n)；本题只需要维护「当前最小的 k 个候选」。候选满后，新元素只需和候选中最大的数比较，因此最合适的数据结构是容量为 k 的大根堆。

堆顶是当前候选里最差的元素：堆未满就直接加入；堆已满且新值小于堆顶时，用新值替换堆顶；否则新值不可能进入最小的 k 个数，直接忽略。

不变量是：扫描完前 i 个元素后，堆中保存这 i 个元素里最小的 min(i, k) 个，堆顶是其中最大值。堆满时，若 value >= top，堆内已有 k 个数不大于它；若 value < top，淘汰 top 后恰好保留新的前 k 小。因此扫描结束时堆中就是答案。

选择大根堆是为了获得 O(n log k) 的最坏时间，并支持数据流式输入。若面试官明确追求平均 O(n) 且允许修改数组，可以再讨论快速选择；本文保留更稳定、适用面更广的堆解法。

解题步骤

  1. k = 0 时直接返回空数组，避免访问不存在的堆顶。
  2. 创建大根堆，保证堆顶始终是当前候选中的最大值。
  3. 顺序扫描数组：堆大小不足 k 时入堆；否则只在新值小于堆顶时替换。
  4. 扫描结束后导出堆中全部元素。题目不要求结果有序，无需再排序。

例如 [1,3,5,7,2,4,6,8]、k=4：前四个数入堆后堆顶为 7；2 替换 7，4 再替换 5，6 和 8 被丢弃，最终候选集合为 {1,2,3,4}。

代码实现

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }

        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int value : arr) {
            if (maxHeap.size() < k) {
                maxHeap.offer(value);
            } else if (value < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(value);
            }
        }

        int[] answer = new int[k];
        int index = 0;
        for (int value : maxHeap) {
            answer[index++] = value;
        }
        return answer;
    }
}

import "container/heap"

type maxHeap []int

func (h maxHeap) Len() int           { return len(h) }
func (h maxHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h maxHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *maxHeap) Push(value any) {
    *h = append(*h, value.(int))
}

func (h *maxHeap) Pop() any {
    old := *h
    last := old[len(old)-1]
    *h = old[:len(old)-1]
    return last
}

func smallestK(arr []int, k int) []int {
    if k == 0 {
        return []int{}
    }

    h := &maxHeap{}
    for _, value := range arr {
        if h.Len() < k {
            heap.Push(h, value)
        } else if value < (*h)[0] {
            heap.Pop(h)
            heap.Push(h, value)
        }
    }
    return []int(*h)
}

复杂度分析

  • 时间复杂度：O(n log k)。每个元素最多触发常数次堆操作，单次操作为 O(log k)；导出无序结果为 O(k)。
  • 空间复杂度：O(k)。堆最多保存 k 个元素；返回数组属于结果空间。

关键点总结

  • 求最小 Top K 使用大根堆，因为堆顶承担的是「最先被淘汰者」，不是最优答案。
  • 只有 value < heap.top 才替换；相等时替换不会改变答案，只会多做操作。
  • 堆维护的是一个多重集合，重复值不能去重；题目也不要求输出有序。
  • 面试中要能说明权衡：全排序最简单，堆有稳定的 O(n log k) 且支持数据流，快速选择平均 O(n) 但会改数组并存在最坏退化。

易错点总结

  • 使用小根堆：堆顶会是候选中最小的数，无法在新元素到来时淘汰最差候选。
  • 堆满后无条件替换：[1,2,3,100]、k=3 会错误地用 100 换掉 3。
  • 漏掉 k=0：第一次比较堆顶时会访问空堆。
  • 比较器写成 b - a：通用整数范围下可能溢出；Java 直接使用 Comparator.reverseOrder()。
  • 先去重或强制排序答案：[2,2,2]、k=2 的答案必须保留两个 2，而结果顺序可以任意。

相似题目

题目 难度 考察点
215. 数组中的第K个最大元素 中等 只求第 k 大这一个值，堆方向与本题相反
347. 前 K 个高频元素 中等 比较键从数值换成先统计出的出现次数
692. 前K个高频单词 中等 频次相同再按字典序，需要写复合比较器
973. 最接近原点的 K 个点 中等 比较键是平方距离，可省去开方
LCR 060. 前 K 个高频元素 中等 347 的同题改编，练哈希计数与堆的组合
LCR 076. 数组中的第 K 个最大元素 中等 215 的同题改编，适合专练快速选择的划分实现
剑指 Offer 40. 最小的k个数 简单 与本题完全同构，可直接复用大根堆写法