输入整数数组 arr ,找出其中最小的 k 个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
示例 1:
输入:arr = [3,2,1], k = 2
输出:[1,2] 或者 [2,1]
示例 2:
输入:arr = [0,1,2,1], k = 1
输出:[0]
思想:实现一个大根堆,通过维护大根堆,实现升序排序来找到最小的k个数。
import ( "container/heap" ) type IntHeap []int func(h IntHeap) Len() int{ return len(h) } func(h IntHeap) Less(i,j int) bool{ return h[i]>h[j] } func(h IntHeap) Swap(i,j int){ h[i],h[j]=h[j],h[i] } func(h *IntHeap) Push(x interface{}){ *h = append(*h,x.(int)) } func(h *IntHeap) Pop() interface{}{ old := *h n:=len(old) x := old[n-1] *h = old[0:n-1] return x } func getLeastNumbers(arr []int, k int) []int { if k ==0{ return []int{} } h := make(IntHeap,k) hp := &h copy(h,IntHeap(arr[:k+1])) heap.Init(hp) for i:=k;i<len(arr);i++{ if arr[i]<h[0]{ heap.Pop(hp) heap.Push(hp,arr[i]) } } return h }
这里要注意大根堆的实现方法,以及使用方式。
题目来源:https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof