用 Go 剑指 Offer 40. 最小的k个数（Top K 问题）

手机

iphone11大小尺寸是多少？苹果iPhone11和iPhone13的区别是什么？

警方通报辅警执法直播中被撞飞：犯罪嫌疑人已投案

家电

用 Go 剑指 Offer 40. 最小的k个数（Top K 问题）

2023-04-10 11:58:07 来源：博客园

输入整数数组 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]

限制：

0 <= k <= arr.length <= 100000 <= arr[i]<= 10000

来源：力扣（LeetCode）链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

三种方法：

1. 递归快排排序然后输出前K个

2.快排分组检查，直到左分组大小为K

3.建立大根堆

funcgetLeastNumbers(arr []int, kint) []int{     　　if len(arr)==0 || k==0 {        return nil    }    //方法一 基于快排的快速选择    // return quicksearch(arr, 0, len(arr)-1, k)    //方法二 快排 然后取前k个    // quicksort(arr, 0, len(arr)-1)    // return arr[:k]    //方法三  建堆，大根堆    d:=&heapInt{}    for _,v:=range arr {        if d.Len()v {                heap.Pop(d)                heap.Push(d,v)            }        }    }    return *d}// 一次快排寻找分割点func partition(nums []int,i,j int) int {    l,m,r:=i,i,j    for l=nums[m] {                r--        }        for l=j {        return    }    m:=partition(nums, i,j)    quicksort(nums,i,m-1)    quicksort(nums,m+1,j)}// golang 的 heap 接口调用type heapInt []int// 建立接口所需函数//Less  小于就是小跟堆，大于号就是大根堆func (h *heapInt)Less(i,j int)bool {return (*h)[i]>(*h)[j]}func (h *heapInt)Swap(i,j int) {(*h)[i],(*h)[j]=(*h)[j],(*h)[i]}func (h *heapInt)Len() int {return len(*h)}func (h *heapInt)Push(x interface{}) {    *h=append(*h,x.(int))}func (h *heapInt)Pop() interface{} {    t:=(*h)[len(*h)-1]    *h=(*h)[:len(*h)-1]    return t}// 查看堆顶元素func (h *heapInt)Peek() int {    return (*h)[0]}

关键词：

用 Go 剑指 Offer 40. 最小的k个数 （Top K 问题）

用 Go 剑指 Offer 40. 最小的k个数（Top K 问题）