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

微软,Google面试题 (5) —— 查找最小的k个元素

2013年12月02日 ⁄ 综合 ⁄ 共 1393字 ⁄ 字号 评论关闭

输入n个数,找出其中最小的k个。
一般的思路是将这n个数排序,排在最前面的k个数就是答案。这种方法最快时间复杂度为nlog(n)。
如果再开辟一个长度为k的数组。以此读取这n个数,如果k数组没有满,则直接放入k数组中,如果满了,且当前的数比k数组中最大的数要小,那么就用当前的数替换k数组中最大的数。(实际上,k数组是一个大顶堆)。这样,当n个数读取完之后,k数组中就是最小的k个数。这时候的复杂度为nlog(k)。
然后将k数组排序,复杂度为klog(k)。

于是,总的复杂度为(n+k)log(k),书上为n+nlog(k),由于k通常比n小很多,所以这种方法比较快

抱歉!评论已关闭.