典型例题

给定一个无序的数组,找到其中最小的k个数
想这种topK类型的题目,首先我们能想到的就是堆,在这里我们要找的是最小的k个数,那我们是建立大根堆还是小根堆那.
我们假设一下,如果建立的是小根堆该如何进行,小根堆中是最小的k个数,所有顶部位置就是k个数中最小的数,如果这个时候有一个值要进入,到底要不要加入那...所以建立小根堆是错误的,应该建立的是大根堆
我们通过大根堆来完成这个操作,其中大根堆就是最小的k个数,堆顶那就是这k个数中最大的那个数,所以随时有可能会被替换.替换之后然后在进行调整.
核心函数如下

public int[]  f(int[] arr,int k)
{
     int[] kHeap=new int[k];
     for(int i......)
     {
          由前k个元素构成了大根堆
     }
     for(从第k个开始遍历)
     {
          //如果小于堆顶的元素,进入,然后heapify
     }

}

这个就是比较容易立即的方式,此时时间复杂度为O(n*logN)

BFPRT算法

接下来,就是重头戏了,我们来介绍一下时间复杂度为O(n)的算法
在开始之前,我们先做一个小小的转化,我们将这个问题转化为寻找第k小的数,这样最后通过一个O(N)的循环就可以得到结果
1.首先,我们队将整个数组都划分成5个一小组,最后不满5个的话,也化为一组
2.然后我们找出每个小组中的中位数,将所有的中位数组成一个数组
3.通过递归的方式,寻找到这个中位数中的中位数
4,然后根据这个中位数进行parition过程,最后如果result的位置=k,说明result就是第k小的数 如果result>k,说明k在左边,否则在右边
这里先不列出代码,因为过于繁多,然后我们再来分析一下这样的时间复杂度...
帖子先写到这里