现在的位置: 首页 > 综合 > 正文

查找最小的k 个元素

2019年04月26日 ⁄ 综合 ⁄ 共 304字 ⁄ 字号 评论关闭

查找最小的k 个元素
题目:输入n 个整数,输出其中最小的k 个。
例如输入1,2,3,4,5,6,7 和8 这8 个数字,则最小的4 个数字为1,2,3 和4。
ANSWER:
This is a very traditional question...
O(nlogn): cat I_FILE | sort -n | head -n K
O(kn): do insertion sort until k elements are retrieved.

O(n+klogn): Take O(n) time to bottom-up build a min-heap. Then sift-down k-1 times.

思路:第一反应是排序,然后找出最小的k个数即可。但是不同的排序针对本题效率不一样。

抱歉!评论已关闭.