输入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小很多,所以这种方法比较快。