topK问题

为啥TopK这么受欢迎呢？究其原因，还是因为它不仅在AI领域广泛应用，比如max pooling，mAP计算等；还涵盖了算法专业的很多必备知识，比如快速排序，二分查找，分治减治，大小顶堆等；一些适当的变换，还可以考察应聘者的思维灵活度。

简介

从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。

栗子：

从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中，找出最大的k=5个。

从arr[1, 12]={5,3,7,1,8,2,9,4,7,2,6,6} 这n=12个数中，找出最大的k=5个。

方案

排序

排序是最容易想到的方法，将n个数排序之后，取出最大的k个，即为所得。

伪代码：

sort(arr, 1, n);

return arr[1, k];

时间复杂度：O(n*lg(n))

分析：明明只需要TopK，却将全局都排序了，这也是这个方法复杂度非常高的原因。那能不能不全局排序，而只局部排序呢？这就引出了第二个优化方法。

局部排序

不再全局排序，只对最大的k个排序。

冒泡是一个很常见的排序方法，每冒一个泡，找出最大值，冒k个泡，就得到TopK。

伪代码：

for(i=1 to k){

bubble_find_max(arr,i);

}

return arr[1, k];

时间复杂度：O(n*k)

分析：冒泡，将全局排序优化为了局部排序，非TopK的元素是不需要排序的，节省了计算资源。不少朋友会想到，需求是TopK，是不是这最大的k个元素也不需要排序呢？这就引出了第三个优化方法

堆

思路只找到topK,不排序topK

先用前K个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的K个元素

接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。

画外音：n个元素扫一遍，假设运气很差，每次都入堆调整，调整时间复杂度为堆的高度，即lg(k)，故整体时间复杂度是n*lg(k)。

分析：堆，将冒泡的TopK排序优化为了TopK不排序，节省了计算资源。堆，是求TopK的经典算法，那还有没有更快的方案呢？

快速选择

在快速排序中用一步很重要的操作：partition（划分）*操作，从数组中随机选取一个*枢纽元素v ，然后原地移动数组中的元素，使得比v小大元素在v的左边，比v大的元素在v的右边

这个partition操作是原地进行的，需要O(n)的时间，接下来快排排序算法会递归左右两侧的数组。而快速选择算法相当于一个“不完全”的快速排序，因为我们只需要知道最小的k个数是哪些，并不需要知道它们的顺序。

假设经过一次partition操作，枢纽元素位于下表m，也就是说左侧的数组有m个元素，是原数组中最小的m个数那么：

如果k=m,我们就找到了最小的k个数，就是左侧的数组
如果k<m，则最小的k个数一定都在左侧数组中，我们只需对左侧数组递归地partition即可
如果k>m，则左侧数组中的m个数都属于最小的k个数，我们还需要在右侧数组中寻找最小k-m个数，对右侧数组递归地partition即可。