首页 > 其他分享 >用 Go 剑指 Offer 40. 最小的k个数 (Top K 问题)

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

时间:2023-04-10 10:58:31浏览次数:31  
标签:arr return Offer int Top 40 len func heapInt

输入整数数组 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 <= 10000
0 <= arr[i] <= 10000

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

func getLeastNumbers(arr []int, k int) []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()<k {
            heap.Push(d,v)
        }else {
            if d.Peek()>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<r {
        for l<r && nums[r]>=nums[m] {
                r--
        }
        for l<r && nums[l]<=nums[m] {
                l++
        }
        if l<r {
            nums[l],nums[r]=nums[r],nums[l]
        }
    }
    nums[m],nums[l]=nums[l],nums[m]
    
    return l
}

func quicksearch(nums []int,i,j,k int) []int{
    
    t:=partition(nums,i,j)

    if t==k-1 {
        return nums[:k]
    }

    if t<k-1 {
        return quicksearch(nums,t+1,j,k)
    }


    return quicksearch(nums,i,t-1,k)
    
}

func quicksort(nums []int,i,j int) {
    if i>=j {
        return
    }

    m:=partition(nums, i,j)
    quicksort(nums,i,m-1)
    quicksort(nums,m+1,j)
}

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]
}

 

标签:arr,return,Offer,int,Top,40,len,func,heapInt
From: https://www.cnblogs.com/slowlydance2me/p/17302210.html

相关文章

  • 20230409-Python-字符串-day6
    字符串4月9字符串是python中最常见的数据类型,我们可以使用单引号''、双引号""、三引号""""""来创建字符串,只要为变量分配一个值即可#单引号var1='helloword'#双引号var2="helloPython"#三引号,可以换行,如果没有变量名,这就是一个多行注释var......
  • 405 最长公共子序列 线性DP
    视频链接:https://www.bilibili.com/video/BV1EK411K7Eb/ #include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1010;intn,m;chara[N],b[N];intf[N][N];intmain(){cin>>n>>m>>......
  • 【230409-6】由数字1,2,3,4,5组成,没有重复数字的五位数,其中小于50000的偶数共有几个?
    ......
  • Lighting System Design uva11400
    设计一个照明系统,一共有n(n<=1000)种灯泡可供选择,不同种类的灯泡必须用不同的电源,同一种灯泡则可以用一个,输入为一个n,以下n行,每行四个数值,代表电压V,电源费用K,每个灯泡费用C,所需灯泡数量L。n=0为结束标志。为了省钱,你可以把一些灯泡换成电压更高的以节省电源的钱,但不能换成更低的,......
  • 6361.对角线上的质数-340
    对角线上的质数给你一个下标从0开始的二维整数数组nums。返回位于nums至少一条对角线上的最大质数。如果任一对角线上均不存在质数,返回0。注意:如果某个整数大于1,且不存在除1和自身之外的正整数因子,则认为该整数是一个质数。如果存在整数i,使得 nums[i][i]......
  • 力扣---剑指 Offer 16. 数值的整数次方
    实现 pow(x, n) ,即计算x的n次幂函数(即,xn)。不得使用库函数,同时不需要考虑大数问题。 示例1:输入:x=2.00000,n=10输出:1024.00000示例2:输入:x=2.10000,n=3输出:9.26100示例3:输入:x=2.00000,n=-2输出:0.25000解释:2-2=1/22=1/4=0.25 提示:-100.0< x......
  • 6360.等值距离和-340
    等值距离和给你一个下标从0开始的整数数组nums。现有一个长度等于nums.length的数组arr。对于满足nums[j]==nums[i]且j!=i的所有j,arr[i]等于所有|i-j|之和。如果不存在这样的j,则令arr[i]等于0。返回数组arr。示例1:输入:nums=[1,3,1,1,2]输......
  • 【230409-1】记者要为5名志愿者和他们帮助的2位老人拍照,要求排成一排,2位老人相邻但不
    ......
  • 230409 What is a Battery Management System
    WelcometotheStoffelSystemsInsightsvideoseries.I'mEricStoffel,PresidentofStoffelSystems.Inthisseries,we'lldiscussbatterymanagementsystemsasusedinlithium-ionbatterypacks.Let'sbeginwithanintroductiontowhatabat......
  • 401 数字三角形 记忆化搜索
    视频链接:https://www.bilibili.com/video/BV16V411U7Gc/LuoguP1216[USACO1.5][IOI1994]数字三角形NumberTriangles#include<iostream>#include<cstring>#include<algorithm>usingnamespacestd;constintN=1005;intn,a[N][N],f[N][N];intdfs(......