在面试中，TopK是最常被问到的问题之一。有多少种方法？这些解决方案包含哪些优化思路？今天让我和你谈谈。画外音：除非是校招，否则我在面试过程中从来不会问TopK这个问题。问题描述：从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。1.排序排序是最容易想到的方法。将n个数排序后，取出最大的k，即为结果。伪代码：排序（arr，1，n）；returnarr[1,k];时间复杂度：O(n*lg(n))分析：明明只需要TopK，却对整个世界进行了排序，这也是该方法复杂度非常高的原因。不能全局排序，只能局部排序吗？这就引出了第二种优化方法。第二，局部排序不再是全局排序，只是最大的k排序。冒泡是一种很常见的排序方法。对每一个泡泡，求最大值，取k个泡泡，得到TopK。伪代码：for(i=1tok){bubble_find_max(arr,i);}returnarr[1,k];时间复杂度：O(n*k)分析：冒泡，优化全局排序为局部排序，非TopK的元素不需要排序，节省了计算资源。很多朋友会认为需求是TopK。是不是说最大的k个元素不需要排序呢？这就引出了第三种优化方法。3.堆思路：只找TopK，不排序TopK。先用前k个元素生成一个小顶堆。这个小顶堆用来存放当前最大的k个元素。接下来从第k+1个元素开始扫描，与堆顶（堆中最小的元素）比较。如果扫描到的元素大于堆顶，则替换堆顶元素并调整堆，保证堆元素中的k个，始终是当前最大的k个元素。直到扫描完n-k个元素，最终堆中的k个元素就是平凡寻找的TopK。伪代码：heap[k]=make_heap(arr[1,k]);for(i=k+1ton){adjust_heap(heep[k],arr[i]);}returnheap[k];时间复杂度：O(n*lg(k))画外音：扫描一次n个元素，假设运气不好，每次都放入堆中调整，调整时间复杂度到堆高，即lg(k)，所以整体时间复杂度为n*lg(k)。分析：对于堆，优化了冒泡TopK排序，使得TopK不排序，节省了计算资源。堆是一个经典的寻找TopK的算法，那么有没有更快的解决方案呢？4.随机选择随机选择是《算法导论》中的经典算法，其时间复杂度为O(n)，是复杂度的线性方法。不是所有的学生都知道这个方法。为了把算法说的透彻，先说一些前序知识，一个所有程序员都应该熟悉的经典算法：快速排序。画外音：如果有朋友说，“我对quicksort一窍不通，不妨碍我写业务代码”……嗯……除非我是学校招的，否则我从来不问quicksort在面试过程中。默认情况下，所有工程师都知道它；代码是：voidquick_sort(int[]arr,intlow,inthigh){if(low==high)return;inti=partition(arr,low,high);quick_sort(arr,low,i-1);quick_sort(arr,i+1,high);}它的核心算法思想是分而治之。Divide&Conquer将一个大问题转化为若干个子问题（Divide），每个子问题“全部”解决，大问题相应解决（Conquer）。这里的关键词是“两者”。从伪代码可以看出，quicksort递归时，首先将数组按partition分成两部分，两部分“both”都需要再次递归。分而治之有一个特例，叫做reduceandconquer。Reduce&Conquer将一个大问题转化为若干个子问题（Reduce），“只”解决其中一个子问题，大问题也就随之解决（Conquer）。这里的关键词是“只”。二分查找binary_search，BS，是典型的利用减法和治愈思想的算法。其伪代码为：intBS(int[]arr,intlow,inthigh,inttarget){if(low>high)return-1;mid=(low+high)/2;if(arr[mid]==target)returnmid;if(arr[mid]>target)returnBS(arr,low,mid-1,target);elsereturnBS(arr,mid+1,high,target);}从伪代码可以看出，二分查找，一大问题，可以分为两个子问题，左半部分和右半部分，中间有一个元素。至于左右子问题，只需要解决其中一个，递归一次就可以解决二分查找的全局问题。通过对分治法和归约法的描述，可以发现分治法的复杂度普遍大于归约法：快速排序：O(n*lg(n))二分查找：O(lg(n)))话题回来了，快速排序的核心是：i=partition(arr,low,high);这个分区是做什么用的？顾名思义，分区会将整体分成两部分。更具体地说，数组arr中的一个元素（默认为第一个元素t=arr[low]）将作为划分依据将数据arr[low,high]划分为左右两个子数组：一半，均大于t；右半部分小于t；中间位置i为除法元素；以上面TopK数组为例，首先以第一个元素t=arr[low]作为划分依据，对数组进行一次扫描，将数组分成两半：左边一半大于t；右半部分小于t；中间是t；partition返回t的最终位置i。很容易知道分区的时间复杂度是O(n)。画外音：扫描整个数组，比t大的放在左边，比t小的放在右边，最后把t放在中间的N[i]。分区和TopK问题有什么关系？TopK希望找到arr[1,n]中最大的k个数。如果找到第k大的数，做一个分区，然后一次性找到最大的k个数。你数过吗？画外音：即分区左半部分的k个数。问题变成了在arr[1,n]中找到第k个最大的数。返回并查看第一个分区。除法后：i=partition(arr,1,n);如果i大于k，说明arr[i]左边的元素都大于k，所以只递归arr[1，i-1]中第k大的元素即可；如果i小于k，说明第k大的元素在arr[i]的右边，所以递归只需要arr[i+1,n]中第k大的元素就够了；画外音：这段话很重要，多读几遍。这就是随机选择算法randomized_select，RS，其伪代码如下：intRS(arr,low,high,k){if(low==high)returnarr[low];i=partition(arr,low,high);t=i-low;//数组前半部分的元素个数if(t>=k)returnRS(arr,low,i-1,k);//找到前半部分第k大的元素elsereturnRS(arr,i+1,high,k-t);//找后半段第k大的}这是一个典型的归约和治愈算法，递归的两个分支，最后只会执行一个，其时间复杂度为O(n)。再强调一下：分而治之，把大问题分解成小问题，小问题的每一个分支都要递归，比如：快速排序；reduceandconquer，将大问题分解为小问题，小问题只需要递归一个分支，如：二分查找，随机选择；通过随机选择（randomized_select），找到arr[1,n]中第k大的数，然后进行划分得到TopK的结果。5.总结TopK并不难；其思想的优化过程并不简单：全局排序，O(n*lg(n))；局部排序，只对TopK的个数进行排序，O(n*k)；heap，TopK的个数没有排序，O(n*lg(k))；分而治之，每个分支“必须”递归，例如：快速排序，O(n*lg(n))；reduceandconquer，“只要”递归的一个分支，例如：二分查找O(lg(n))，随机选择O(n)；TopK的另一种方案：随机选择+划分；知其然，知其所以然。想法比结论更重要。【本文为专栏作者《58神剑》原创稿件，转载请联系原作者】点此阅读更多该作者好文
