剑指 Offer 40. 最小的k个数 - 力扣(LeetCode)
输入整数数组 arr
,找出其中最小的 k
个数。例如,输入4、5、1、6、2、7、3、8这8个数字,则最小的4个数字是1、2、3、4。
思路:
-
快速划分
-
大根堆
我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小,就把堆顶的数弹出,再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
复杂度:
O(k)
题解:
- 大根堆
class Solution { |
- 快速划分
class Solution { |