首页 > 试题广场 >

最小的K个数

[编程题]最小的K个数
  • 热度指数：1197517 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：，数组中每个数的大小
要求：空间复杂度 ，时间复杂度 O(nlogk)

示例1

输入

[4,5,1,6,2,7,3,8],4

输出

[1,2,3,4]

说明

返回最小的4个数即可，返回[1,3,2,4]也可以
示例2

输入

[1],0

输出

[]
示例3

输入

[0,1,2,1,2],3

输出

[0,1,1]
算法知识视频讲解
添加回答
Python
牛客368539496号头像 牛客368539496号
利用了堆排序的思想，但没有用到堆。先取出tmp = tinput[:k],然后依次遍历后续的元素，依次和tmp中的最大值比较，小于则删除最大值，然后进堆（差不多是这意思）。我不知道python自带的max函数的复杂度，理论上应该时间复杂度大于O（n）。
                                                                         运行时间：29ms超过23.88% 用Python提交的代码
占用内存：6348KB超过3.14%用Python提交的代码

测试后发现我的方法的运行时间比堆排序的运行时间慢很多，和快排几乎一样

发表于 2021-11-18 21:16:37 回复(2)
Python
小李啦啦啦头像 小李啦啦啦
python 22ms：
思路就是整两个数组，不停的交换数据，没有用各路大神的算法，不过很好理解。
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        src_arr = tinput[k:]
        dst_arr = tinput[0:k]
        for s in src_arr:
            for d_idx, d in enumerate(dst_arr):
                if s < d:
                    temp = s
                    s = d
                    dst_arr[d_idx] = temp
        dst_arr.sort()
        return dst_arr
发表于 2021-08-07 16:08:49 回复(0)
Python
牛客590711274号头像 牛客590711274号 
#看了下k和tinput初始格式为int和list[元素为int]
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        tinput.sort()#由于是int元素，不用转变直接sort
        str1 = tinput[0:k]#只要到第k个
        return str1#返回数据

发表于 2021-07-12 17:18:09 回复(0)
Python
彩鳞头像 彩鳞
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if k >len(tinput):
            return []
        else:
            tinput.sort()
            res = tinput[:k:1]
            return res
发表于 2021-07-08 10:48:32 回复(0)
Python
牛客581205746号头像 牛客581205746号
堆实现，通过全部测试例：

class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        L = []
        build = 0
        if k > len(tinput) or k==0:
            return []
        
        for e in tinput:
            if len(L)<k:
                L.append(e)
            if len(L) == k and build == 0:
                self.heapbuild(L, k-1)
                build = 1
                
            if len(L) == k and e < L[0]:
                L[0]=e 
                self.heapadjust(L, 0, k-1)
            
        for j in range(len(L)-1,0,-1):
            L[j],L[0] = L[0],L[j]
            self.heapadjust(L, 0, j - 1)
            
        return L
                
                
        
    def heapbuild(self,a,length):
        for i in range((length+1)// 2 -1,-1,-1):
            self.heapadjust(a, i, length)
    
    def heapadjust(self,a,i,length):
        left = 2*i +1
        right= 2*i +2
        
        largest = i
        
        if left <=length and a[left]>a[largest]:
            largest = left
        if right <=length and a[right]>a[largest]:
            largest = right
            
        if largest !=i:
            a[largest],a[i] = a[i],a[largest]
            self.heapadjust(a,largest,length)

发表于 2021-06-21 17:13:44 回复(0)
Python
牛客860087957号头像 牛客860087957号
思路：1冒泡排序 2切片前K个元素 
n = len(tinput)
if k > n:
    return []
for i in range(n-1, 1, -1):
    for j in range(0, i):
        if tinput[j] > tinput[j+1]:
            tinput[j], tinput[j+1] = tinput[j+1], tinput[j]
return tinput[:k]


编辑于 2021-06-08 21:02:22 回复(0)
Python
陌生荒头像 陌生荒 
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        a =[]
        length = len(tinput)
        if k<=0&nbs***bsp;k>length&nbs***bsp;length == 0:
            return a
        else:
            return sorted(tinput)[:k]
数组排序，切片
发表于 2021-05-19 16:29:37 回复(0)
Python
wengJJ头像 wengJJ
Python
两种思路：
先排序后取值
进行k次取最小值的操作（k次选择排序） 
# -*- coding:utf-8 -*-
class Solution:
    def quickSort(self,nums):
        if not nums:
            return []
        mid = nums[0]
        left = self.quickSort([x for x in nums[1:] if x<mid])
        right = self.quickSort([x for x in nums[1:] if x>=mid])
        return left+[mid]+right
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
#         先排序再取值
        if k>len(tinput):
            return []
        result = self.quickSort(tinput)
        return result[:k]
#         k次选择排序
#         if k>len(tinput):
#             return []
#         res = []
#         for _ in range(k):
#             Min = tinput[0]
#             for num in tinput:
#                 if num < Min:
#                     Min = num
#             res.append(Min)
#             tinput.remove(Min)
#         return res


发表于 2021-04-30 16:10:48 回复(0)
Python
feiyu9372头像 feiyu9372 
python 很简单
if k > len(tinput): 
    return [] 
else: 
    return sorted(tinput)[0:k]
发表于 2021-04-28 17:16:51 回复(0)
Python
牛客640734838号头像 牛客640734838号
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        res=[]
        if len(tinput)<k :return res
        tinput.sort() 
        return tinput[:k]
编辑于 2021-04-28 14:25:49 回复(0)
Python
牛客541273514号头像 牛客541273514号 
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if not tinput&nbs***bsp;k<0&nbs***bsp;k>len(tinput):
            return []
        order=sorted(tinput)
        return order[:k]


发表于 2021-04-20 23:04:11 回复(0)
Python
你那么_特别头像 你那么_特别
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        lst=[(i,j) for i,j in enumerate(sorted(tinput))]
        if k>len(lst):
            return []
        elif k<=len(lst):
            return [k for h,k in lst[:k]]
简单就好。空间复杂度没考虑；
发表于 2021-04-20 21:32:27 回复(0)
Python
牛客695191337号头像 牛客695191337号 
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        if k > len(tinput)&nbs***bsp;k==0:
            return []
        else:
            tinput.sort()
            return tinput[:k]

发表于 2021-04-18 15:48:08 回复(0)
Python
牛客659423677号头像 牛客659423677号 
# python一行，溜了溜了
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        return [] if k>len(tinput) else sorted(tinput)[:k]

发表于 2021-04-01 16:51:09 回复(0)
Python
西瓜566头像 西瓜566
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        tinput.sort()
        if k > len(tinput):
            return []
        return tinput[:k]
发表于 2021-03-28 14:23:11 回复(0)
Python
Eite头像 Eite
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
#         write code here
        if(k>len(tinput)):
            return []
        tinput.sort()
        return tinput[:k]
发表于 2021-03-26 21:48:29 回复(0)
Python
123hahaha头像 123hahaha
先快排，再切片。python： 
# -*- coding:utf-8 -*-
class Solution:
    def fast_sort(self, arr):
        if len(arr) < 2:
            return arr
        else:
            pivot = arr[0]
            return self.fast_sort([x for x in arr[1:] if x <= pivot]) + [pivot] + self.fast_sort([x for x in arr[1:] if x > pivot])
    
    def GetLeastNumbers_Solution(self, tinput, k):
        if k > len(tinput):
            return []
        else:
            sorted_tinput = self.fast_sort(tinput)
            return sorted_tinput[:k]
        # write code here


发表于 2021-03-11 15:06:12 回复(0)
Python
牛客442032212号头像 牛客442032212号 

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        n=sorted(tinput)
        if k<=len(n):
            a=[i for i in n[0:] if i<=k]
            return a[:k]
        else:
            return []

可能难在了排序上吧，不过用python有直接的排序函数好受好多

编辑于 2021-03-06 10:34:37 回复(0)
Python
牛客297477155号头像 牛客297477155号 
# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        return [] if k > len(tinput) else sorted(tinput)[:k] 

发表于 2020-11-14 11:52:50 回复(0)
Python
牛客97191755号头像 牛客97191755号
使用python堆队列算法库 heapq 
import heapq
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        if tinput == [] or k > len(tinput):
            return []
        return(heapq.nsmallest(k,tinput))


编辑于 2020-11-12 10:19:23 回复(0)
提交观点

问题信息

分治 堆 排序
难度：
96条回答 186505浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号