LeetCode 面试题 17.14. 最小K个数

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 面试题 17.14. 最小 K 个数

思路分析

排序

大顶堆

快速选择算法

参考代码

func smallestK(arr []int, k int) []int {
	quickSelect(arr, 0, len(arr)-1, k)
	return arr[:k]
}

// 快速选择算法
func quickSelect(arr []int, left, right, k int) {
	if left < right {
		pivotIndex := partition(arr, left, right)
		if pivotIndex == k {
			return
		} else if pivotIndex < k {
			quickSelect(arr, pivotIndex+1, right, k)
		} else {
			quickSelect(arr, left, pivotIndex-1, k)
		}
	}
}

// 分区函数
func partition(arr []int, left, right int) int {
	pivot := arr[right]
	i := left
	for j := left; j < right; j++ {
		if arr[j] < pivot {
			arr[i], arr[j] = arr[j], arr[i]
			i++
		}
	}
	arr[i], arr[right] = arr[right], arr[i]
	return i
}

时间复杂度：O (n)，平均情况下，快速选择的时间复杂度为 O (n)。

空间复杂度：O (1)，不考虑递归栈的空间。

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 {
	var res []int
	if k <= 0 || len(arr) == 0 {
		return res
	}
	if k >= len(arr) {
		return arr
	}
	// 初始化大顶堆
	h := &maxHeap{}
	// 前 k 个入堆
	for i := 0; i < k; i++ {
		heap.Push(h, arr[i])
	}
	// 遍历后续元素，维护堆大小为 k
	for i := k; i < len(arr); i++ {
		if arr[i] < (*h)[0] {
			heap.Pop(h)
			heap.Push(h, arr[i])
		}
	}

	for h.Len() > 0 {
		res = append(res, heap.Pop(h).(int))
	}
	return res
}

时间复杂度：O(n log k)，其中 n 为数组长度，k 为要取的元素个数。

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

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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