算法题：topK给出3种解法？

Answer 1

参考回答：

1）局部淘汰法 -- 借助“冒泡排序”获取TopK

思路：（1）可以避免对所有数据进行排序，只排序部分；（2）冒泡排序是每一轮排序都会获得一个最大值，则K轮排序即可获得TopK。

时间复杂度空间复杂度：（1）时间复杂度：排序一轮是O(N)，则K次排序总时间复杂度为：O(KN)。（2）空间复杂度：O(K)，用来存放获得的topK，也可以O(1)遍历原数组的最后K个元素即可。

2）局部淘汰法 -- 借助数据结构"堆"获取TopK

思路：（1）堆：分为大顶堆（堆顶元素大于其他所有元素）和小顶堆（堆顶其他元素小于所有其他元素）。（2）我们使用小顶堆来实现。（3）取出K个元素放在另外的数组中，对这K个元素进行建堆。（4）然后循环从K下标位置遍历数据，只要元素大于堆顶，我们就将堆顶赋值为该元素，然后重新调整为小顶堆。（5）循环完毕后，K个元素的堆数组就是我们所需要的TopK。

时间复杂度与空间复杂度：（1）时间复杂度：每次对K个元素进行建堆，时间复杂度为：O(KlogK)，加上N-K次的循环，则总时间复杂度为O((K+(N-K))logK)，即O(NlogK)，其中K为想要获取的TopK的数量N为总数据量。（2）空间复杂度：O(K)，只需要新建一个K大小的数组用来存储topK即可

3）分治法 -- 借助”快速排序“方法获取TopK

思路：（1）比如有10亿的数据，找处Top1000，我们先将10亿的数据分成1000份，每份100万条数据。（2）在每一份中找出对应的Top 1000，整合到一个数组中，得到100万条数据，这样过滤掉了999%%的数据。（3）使用快速排序对这100万条数据进行”一轮“排序，一轮排序之后指针的位置指向的数字假设为S，会将数组分为两部分，一部分大于S记作Si，一部分小于S记作Sj。（4）如果Si元素个数大于1000，我们对Si数组再进行一轮排序，再次将Si分成了Si和Sj。如果Si的元素小于1000，则我们需要在Sj中获取1000-count(Si)个元素的，也就是对Sj进行排序（5）如此递归下去即可获得TopK。

时间复杂度与空间复杂度：（1）时间复杂度：一份获取前TopK的时间复杂度：O((N/n)logK)。则所有份数为：O(NlogK)，但是分治法我们会使用多核多机的资源，比如我们有S个线程同时处理。则时间复杂度为：O((N/S)logK)。之后进行快排序，一次的时间复杂度为：O(N),假设排序了M次之后得到结果，则时间复杂度为：O(MN)。所以 ，总时间复杂度大约为O(MN+(N/S)logK) 。（2）空间复杂度：需要每一份一个数组，则空间复杂度为O(N)。