查找最小的k个数

一个整型数组,有n个元素,可以含有重复元素。 查找该数组中最小的k个数。

(1)对数组快速排序,然后从前往后依次挑出最小的k个元素,时间复杂度:nlogn + k = nlogn

(2)设置一个容量是 k 的临时数组,扫描目的数组,如果临时数组元素个数小于k,直接填入临时数组,如果临时数组元素个数大于k,找出临时数组的最大的元素,如果扫描的元素大于或等于最大元素直接过滤掉,如果小于,就替换掉这个最大元素。 时间复杂度是:k + (n - k)*k = nk

(3)相比较(2)的差异,当临时数组填满k个元素后,立即建成最大堆(建堆时间复杂度O(k)),以后,每次扫描的元素大于或等于堆顶,直接过滤掉,否则替换堆顶并调整堆。

         时间复杂度是:k + k + (n - k)*logk = nlogk

(4)把原始数组建成最小堆,删除k次堆顶,即吐出k个最小值。 时间复杂度是 n + k*logn = max( n, k*logn)

原文地址:https://www.cnblogs.com/joyeehe/p/7943269.html