题解 | #$O(N)$解法的最小K个数#
最小的K个数
https://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf
顾名思义，其实是用了空间换时间，但是其实也是常数空间（我也是O1！但其实肯定比顶堆用的多）；
但考虑到n可以到10000，顶堆需要至少logk，那这个方法还是有一点意义的。
别的不多说，上代码
class Solution: def GetLeastNumbers_Solution(self , input: List[int], k: int) -> List[int]: # write code here if input == [] or k == 0: return None n = len(input) count = [0]*1001 for i in range(n): count[input[i]] += 1 res = [] for i in range(1001): while k > 0 and count[i] > 0: res.append(i) k -= 1 count[i] -= 1 return res有限数据下确实很唬人，hhhhh
但实际分析，只有n大于1000开始，这个算法才会快一点，这个和val的取值范围有关，如果是10000的话，其实是快的
时间复杂度)
，空间复杂度)
。（嘿嘿）
投递建信金科等公司10个岗位 >