LeetCode 剑指 Offer 40. 最小的k个数

Categories:

Tags:

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

题目描述

✅ 剑指 Offer 40. 最小的k个数

思路分析

大顶堆

参考代码

// 大顶堆
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 any)        { *h = append(*h, x.(int)) }
func (h *MaxHeap) Pop() any {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

// getLeastNumbers
func inventoryManagement(nums []int, k int) []int {
	if len(nums) <= 0 || k == 0 {
		return []int{}
	}

	h := &MaxHeap{}
	heap.Init(h)

	for _, num := range nums {
		if h.Len() < k {
			heap.Push(h, num)
		} else if num < (*h)[0] {
			heap.Pop(h)
			heap.Push(h, num)
		}
	}

	var res []int
	for _, v := range *h {
		res = append(res, v)
	}

	return res
}

时间复杂度：O(n log k)，每次操作堆是 O(log k)，最多 n 次插入。

空间复杂度：O(k)，堆的大小为 k。

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

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