首页 > 试题广场 >

最小的K个数

[编程题]最小的K个数

热度指数：1197621 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围： $0\le k,n \le 10000$ ，数组中每个数的大小 $0 \le val \le 1000$

要求：空间复杂度 $O(n)$ ，时间复杂度 $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]

算法知识视频讲解

Python3

lintoon

#感觉如果用了sort，那这题都不叫题，只能写着体现下排序的逻辑

class Solution:

def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:

# write code here

l=[]

while input:

l.append(input.pop(input.index(min(input))))

return l[:k]

编辑于 2024-03-28 13:28:37 回复(0)

Python3

勇敢小小小牛

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        res = []
        for _ in range(k):
            minre = min(input)
            input.remove(minre)
            res.append(minre)            
        return res

编辑于 2024-03-14 10:46:06 回复(0)

Python3

牛客429226965号

class Solution:

def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:

# write code here

# 冒泡的时间复杂度是mk的

# 最小堆

def minHeapfy(alist, length, root): # root 保证root节点上是大小有序得

left = root * 2 + 1

right = root * 2 + 2

minRoot = root # 这边必须是三个中最小得

if left < length and alist[left] < alist[minRoot]:

minRoot = left

if right < length and alist[right] < alist[minRoot]:

minRoot = right

if minRoot != root:

alist[minRoot], alist[root] = alist[root], alist[minRoot]

minHeapfy(alist, length, minRoot)

def bulidMinHeap(alist):

n = len(alist)

parent = (n-1)//2

for i in range(parent, -1, -1):

minHeapfy(alist, n, i)

if k == 0:

return []

if k >= len(input):

return input

bulidMinHeap(input)

n = len(input)

for i in range(n-1, n-1-k, -1):

input[0], input[i] = input[i], input[0]

minHeapfy(input, i, 0)

return input[-k:]

发表于 2023-08-03 16:37:27 回复(0)

Python3

pzq

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        if k == 0:
            return []
        list_min = input[:k]
        for i in range(k, len(input)):
            val = input[i]
            val_max = max(list_min)
            if val < val_max:
                ind = list_min.index(val_max)
                list_min[ind] = val
        list_min.sort()
        return list_min

发表于 2023-06-15 23:45:11 回复(0)

Python3

去网吧偷显卡

class Solution:
    # 实现堆排序
    def sink(self, input, i, n):
        j=2*i+1
        while j<n:
            if j<n-1 and input[j]>input[j+1]:
                j+=1
            if input[j]<input[i]:
                input[i], input[j]=input[j], input[i]
            i=j
            j=2*i+1

    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        if len(input)==0:
            return []
        n=len(input)
        for i in range((n-1)//2, -1, -1):
            self.sink(input, i, n)
        ans=[]
        for _ in range(min(k, n)):
            ans.append(input[0])
            input[0]=input[-1]
            input.pop()
            self.sink(input, 0, len(input))
        return ans

发表于 2023-05-24 19:24:22 回复(0)

Python3

threedog

def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:

res = []

for i in range(0, k):

res.append(input.pop(input.index(min(input))))

return res

这个思路不需要排序，每次取最小值放到结果里，再把数组里的这个值原移除掉，k是几久执行几次。

当然，用python属实是作弊了

发表于 2023-03-29 23:46:52 回复(0)

Python3

曰无衣bupt

有些题是不是不适合python……

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        return sorted(input)[:k]

发表于 2023-01-27 21:40:21 回复(2)

Python3

秋叶红霜CCCCCC

import heapq


class Solution:
    def GetLeastNumbers_Solution(self, input: List[int], k: int) -> List[int]:
        heapq.heapify(input)
        return heapq.nsmallest(k, input)

发表于 2022-11-03 21:50:42 回复(0)

Python3

努力搞钱

class Solution:
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        # write code here
        input.sort()
        return input[0:k]

发表于 2022-11-01 16:39:23 回复(0)

Python3

Meizhiheng

return sorted(input)[:k]

发表于 2022-10-16 16:11:40 回复(0)

Python3

JianYue

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param input int整型一维数组 
# @param k int整型 
# @return int整型一维数组
#
class Solution:
    def __init__(self):
        """构建小根堆"""
        self.heap = []
        
    def push(self, num: int):
        tmp = self.heap
        tmp.append(num)
        child = len(tmp) - 1
        # 平衡小根堆
        while child >0:
            parent = (child-1)//2
            if tmp[parent] > tmp[child]:
                tmp[parent], tmp[child] = tmp[child], tmp[parent]
                child = parent
            else:
                break
        
    def pop(self):
        tmp = self.heap
        tmp[0], tmp[-1] = tmp[-1], tmp[0]
        ret = tmp.pop()
        # 平衡小根堆
        parent = 0
        while parent < len(tmp):
            child = parent * 2 + 1
            if child >= len(tmp):
                break
            if child + 1 < len(tmp) and tmp[child] > tmp[child+1]:
                child = child + 1
            if tmp[child] < tmp[parent]:
                tmp[child], tmp[parent] = tmp[parent], tmp[child]
                parent = child
            else:
                break
        return ret
    
    def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
        ret = []
        if len(input) < k:
            return ret
        for i in input:
            self.push(i)
        for i in range(k):
            min = self.pop()
            ret.append(min)
        return ret

发表于 2022-09-25 11:44:10 回复(0)

Python3

蓝鲸与风

class Solution:
    def GetLeastNumbers_Solution(self , inputs: List[int], k: int) -> List[int]:
        import heapq#小顶堆
        res = []
        if len(inputs)>=k and k>0:
            q=[]
            for i in range(k):#初始化大顶堆，默认小顶推
                heapq.heappush(q,-inputs[i])#绝对值大的在上面，返回其相反数即可
            for i in range(k,len(inputs)):#剩余元素入堆
                #每次与大顶推的第一个比，如果比最小的k个中的最大值小，那就加入
                if -q[0] > inputs[i]:#-q[0]就是一个正数，最小的k个里面的最大的
                    heapq.heapreplace(q,-inputs[i])
                    #先弹出当前的最小元素，而后将-inputs[i]插入到heapq序列当中
            for i in range(k):
                res.append(-q[0])#每次取堆顶元素的相反数，也就是最小的k个中最大的那个
                heapq.heappop(q)#从heapq序列中弹出第一个元素（最小值）
        return res

发表于 2022-08-20 10:51:22 回复(1)

Python3

苏堤

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param input int整型一维数组
# @param k int整型
# @return int整型一维数组
#
class Solution:
def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
# write code here
def quicksort(arr):
if len(arr) >=2:
mid=arr[0]
left,right= [],[]
arr.remove(mid)
for num in arr:
if num >=mid:
right.append(num)
else:
left.append(num)
return quicksort(left) +[mid]+quicksort(right)
else:
return arr

res=[]
if(k<=0 or k >len(input)):
return res
else:
res= quicksort(input)
return res[:k]

发表于 2021-12-18 01:20:25 回复(0)

Python3

牛客948260293号

#這個是性能最好的算法吧。

class Solution:

def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]:
temp = []
if k > len(input):return temp
index = 0
size = len(input)
num = 1
while index < k :
for num in range(0,size -index-1):
if input[num] < input[num+1]:
input[num],input[num+1] = input[num+1],input[num]
temp.append(input[size -index -1])
index += 1
return temp

发表于 2021-11-23 09:05:26 回复(0)

Python3

周雨欣_KatherineZhou

method 1: sort（）nlogn 但是结果并不需要排好序，所以做了很多无用功

method 2: 快排partition nlogk 但是多次访问数据，如果n很大，尽量想避免使用过多的数据

# -*- coding:utf-8 -*-
class Solution:
def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if not tinput:
return []
return self.partition(0, len(tinput)-1,tinput,k)

def partition(self, start, end, tinput, k):
if start > end:
return tinput[:k]

left, right = start, end
pivot = tinput[(start + end)//2]

while left <= right:
while left <= right and tinput[left] < pivot:
left += 1
while left <= right and tinput[right] > pivot:
right -= 1

if left <= right:
tinput[left], tinput[right] = tinput[right], tinput[left]
left += 1
right -= 1

if k <= right:
self.partition(start, right, tinput, k)
if k >= left:
self.partition(left, end, tinput, k)

return tinput[:k]

发表于 2021-09-25 12:39:51 回复(0)

Python3

牛客47180554号

萌新有个疑问，这里能不能直接调用python自带的排序函数呢？

如果可以的话就直接输出结果就好了……

# -*- coding:utf-8 -*-
class Solution:
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        return sorted(tinput)[:k]

发表于 2021-08-25 14:02:19 回复(5)

Python3

牛客45854653号

class Solution:
    def quicksort(self,nums):
        if len(nums)<2:
            return nums
        else:
            flag=nums[0]
            less=[i for i in nums[1:] if i <flag]
            more=[i for i in nums[1:] if i>= flag]
            return self.quicksort(less)+[flag]+self.quicksort(more)
    def GetLeastNumbers_Solution(self, tinput, k):
        if k>len(tinput):
            return []
        else:
            alist=self.quicksort(tinput)
            return alist[:k]

发表于 2021-08-24 15:51:40 回复(0)

Python3

大霞上仙

# -*- coding:utf-8 -*-
class Solution:

def sort(self, a, low, high):
temp = a[low]
while low < high:
while low < high and temp <= a[high]:
high -= 1

a[low] = a[high]
while low < high and temp >= a[low]:
low += 1
a[high] = a[low]
a[low] = temp
return low

def headN(self, a, low, high, k):

if low < high:
pos = self.sort(a, low, high)
length = pos-low +1
if length == k:
return
elif length > k:
self.headN(a,low,pos-1,k)
else:
self.headN(a, pos+1, high, k-length )


def GetLeastNumbers_Solution(self, tinput, k):
# write code here
if len(tinput)<=k:
return tinput
self.headN(tinput, 0, len(tinput)-1, k)
return tinput[0:k]

发表于 2021-08-15 18:39:06 回复(0)

提交观点

问题信息

分治堆排序

难度：

21条回答 3173收藏 186510浏览

通过挑战的用户

查看代码

牛客3340351号

2023-03-13 15:46:59
HY_comeON

2023-03-09 09:29:58
Elastic...

2023-02-26 11:56:24
牛客46027...

2023-02-25 17:15:38
牛客58768...

2023-02-23 17:07:36

最小的K个数

输入

输出

说明

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题