LeetCode 面试题 17.14. 最小K个数

Categories:

题目描述
思路分析
1. 解法一：最大堆（推荐）
2. 解法二：快速选择
相似题目

题目描述

✅ 面试题 17.14. 最小 K 个数

思路分析

解法一：最大堆（推荐）

核心思路：

维护一个大小为 k 的最大堆（大顶堆），堆顶始终是当前 k 个最小数中最大的那个。

遍历数组时，若当前元素小于堆顶，说明堆顶不属于最终答案，弹出堆顶并将当前元素入堆。

遍历结束后，堆中剩余的 k 个元素即为答案。

复杂度分析：

时间复杂度：O(n log k)，其中 n 为数组长度，每次堆操作为 O(log k)。

空间复杂度：O(k)，堆中最多存储 k 个元素。

import java.util.PriorityQueue;

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        // 大顶堆：堆顶为当前 k 个最小数中最大的元素
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b - a);
        // 先将前 k 个元素加入堆
        for (int i = 0; i < k; i++) {
            maxHeap.offer(arr[i]);
        }
        // 遍历剩余元素，若小于堆顶则替换
        for (int i = k; i < arr.length; i++) {
            if (arr[i] < maxHeap.peek()) {
                maxHeap.poll();
                maxHeap.offer(arr[i]);
            }
        }
        // 将堆中元素写入结果数组
        int[] res = new int[k];
        for (int i = 0; i < k; i++) {
            res[i] = maxHeap.poll();
        }
        return res;
    }
}

import "container/heap"

// maxHeap 实现大顶堆
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(x interface{}) {
	*h = append(*h, x.(int))
}

func (h *maxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func smallestK(arr []int, k int) []int {
	if k == 0 || len(arr) == 0 {
		return []int{}
	}
	// 初始化大顶堆，放入前 k 个元素
	h := &maxHeap{}
	for i := 0; i < k; i++ {
		heap.Push(h, arr[i])
	}
	// 遍历剩余元素，若小于堆顶则替换堆顶
	for i := k; i < len(arr); i++ {
		if arr[i] < (*h)[0] {
			heap.Pop(h)
			heap.Push(h, arr[i])
		}
	}
	// 将堆中元素写入结果
	res := make([]int, k)
	for i := 0; i < k; i++ {
		res[i] = heap.Pop(h).(int)
	}
	return res
}

解法二：快速选择

核心思路：

借助快排的 partition 思路，每次将数组以基准值（pivot）分成两部分：左侧均小于 pivot，右侧均大于等于 pivot。

若 pivot 落在下标 k 处，则 arr[0..k-1] 即为最小的 k 个数（无需排序）。

根据 pivot 下标与 k 的大小关系，只递归一侧，平均时间复杂度 O(n)。

复杂度分析：

时间复杂度：O(n)，其中 n 为数组长度，平均情况下快速选择为 O(n)，最坏 O(n²)。

空间复杂度：O(log n)，递归调用栈的平均深度。

class Solution {
    public int[] smallestK(int[] arr, int k) {
        if (k == 0) {
            return new int[0];
        }
        quickSelect(arr, 0, arr.length - 1, k);
        // partition 完成后，arr[0..k-1] 即为最小的 k 个数
        int[] res = new int[k];
        System.arraycopy(arr, 0, res, 0, k);
        return res;
    }

    private void quickSelect(int[] arr, int left, int right, int k) {
        if (left >= right) {
            return;
        }
        int pivotIndex = partition(arr, left, right);
        if (pivotIndex == k) {
            return;
        } else if (pivotIndex < k) {
            // 最小的 k 个数还需要从右侧找
            quickSelect(arr, pivotIndex + 1, right, k);
        } else {
            // pivot 下标超过 k，只需处理左侧
            quickSelect(arr, left, pivotIndex - 1, k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        int pivot = arr[right];
        int i = left;
        for (int j = left; j < right; j++) {
            // 将小于 pivot 的元素移到左侧
            if (arr[j] < pivot) {
                int tmp = arr[i];
                arr[i] = arr[j];
                arr[j] = tmp;
                i++;
            }
        }
        // 将 pivot 放到最终位置
        int tmp = arr[i];
        arr[i] = arr[right];
        arr[right] = tmp;
        return i;
    }
}

func smallestK(arr []int, k int) []int {
	if k == 0 {
		return []int{}
	}
	quickSelect(arr, 0, len(arr)-1, k)
	// partition 完成后，arr[0..k-1] 即为最小的 k 个数
	return arr[:k]
}

// quickSelect 通过快速选择将最小的 k 个元素移到数组前 k 位
func quickSelect(arr []int, left, right, k int) {
	if left >= right {
		return
	}
	pivotIndex := partition(arr, left, right)
	if pivotIndex == k {
		return
	} else if pivotIndex < k {
		// 最小的 k 个数还需要从右侧找
		quickSelect(arr, pivotIndex+1, right, k)
	} else {
		// pivot 下标超过 k，只需处理左侧
		quickSelect(arr, left, pivotIndex-1, k)
	}
}

// partition 以 arr[right] 为基准将数组分区，返回基准最终下标
func partition(arr []int, left, right int) int {
	pivot := arr[right]
	i := left
	for j := left; j < right; j++ {
		// 将小于 pivot 的元素移到左侧
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	// 将 pivot 放到最终位置
	arr[i], arr[right] = arr[right], arr[i]
	return i
}

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	快速选择 / 堆
剑指 Offer 40. 最小的k个数	简单	堆 / 快速选择
347. 前 K 个高频元素	中等	堆 / 桶排序
692. 前K个高频单词	中等	堆 / 哈希表
973. 最接近原点的 K 个点	中等	堆 / 快速选择
1337. 矩阵中战斗力最弱的 K 行	简单	堆 / 二分查找
378. 有序矩阵中第 K 小的元素	中等	堆 / 二分查找

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/93040297