本文转载自微信公众号“bigsai”，作者：大哥。转载本文请联系bigsai公众号。前言大家好，我是大塞哥，好久不见，好想你们啊？？！今天给大家分享一个TOPK问题，不过我这里考虑的不是特别大的分布式解，一个普通的算法问题。首先搞清楚topK问题是什么？topK问题是找到序列中前k个最大（或最小）的数。topK问题和第K大（或小）问题的解题思路大致相同。TopK问题是一个非常经典的问题，无论是笔试还是面试都出现得非常非常频繁（千万不要说谎）。接下来，从小白的出发点，我觉得topK就是找topK的问题，下面我们一起认识一下TopK吧！目前TopK问题的解法与第K大问题的解法类似。这里，我们就强行扣除215数组的第k大元素作为解法的演示。大家可以看看这个程序员必知的十大排序，对学习很有帮助！排序方法找到TopK，并对TopK进行排序。你要我找TopK做什么？不只是TopK，你要多少，我给你有多少，给你排序。我最熟悉哪种排序？如果你想到冒泡排序O(n^2)，那你就粗心了。如果使用O(n^2)级别的排序算法，也需要对其进行优化。其中，冒泡排序和简单选择排序可以在每一遍中依次确定一个最大（最小）值，所以不需要把所有的数据都排序出来，只需要执行K次，所以时间这个算法的复杂度也是O(nk)。这里回顾一下冒泡排序和简单选择排序的区别：冒泡排序和简单选择排序都是多次pass，每次pass可以确定一个最大值或者最小值。不同的是，气泡在枚举过程中只和自己比较，如果比后者大，则交换；而简单的选择就是每次标记一个最大或最小的数和位置，然后用本次旅行的最后一个位置数与之交换（每次确定一个数的枚举范围就是slowslowdown）。我们用一张图来表示这个过程：下面给大家上代码。简单的选择上图每次都选择最小值，实现的时候每次都选择最大值。//交换数组中的两个元素privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}//冒泡排序实现publicintfindKthLargest1(int[]nums,intk){for(inti=nums.length-1;i>=nums.length-k;i--)//这里只有k次{for(intj=0;jnums[j+1])//与右邻比较{swap(nums,j,j+1);}}}returnnums[nums.length-k];}//简单选择实现publicintfindKthLargest2(int[]nums,intk){for(inti=0;inums[max]){max=j;//替换最小位置}}if(max!=i){swap(nums,i,max);//与第i个位置交换}}returnnums[k-1];}当然也可以使用快速排序、归并排序甚至堆排序。这些排序的时间复杂度为O(nlogn)，即对所有数据排序后直接返回结果，这部分不再详述。您可以调整api或手写排序。两种思路来说，除了K极小的情况，O(nk)更快，大多数情况下，O(nlogn)其实更快。不过，从O(n^2)想到O(nk)还是很有收获的。.基于堆排序优化，需要了解堆相关的知识。之前写过优先队列和堆排序。在此不再赘述。队列说堆排序O(nlogn)是对所有元素排序然后取前k，其实我们来分析一下堆排序的过程和几个注意点：堆的数据结构分为大根堆和小根堆，小根堆是指父节点的值小于子节点的值，大根堆是指父节点的值大于子节点的值子节点。在这里，必须使用大根堆。堆看起来像树状结构，但堆是一棵完全二叉树。用数组存储效率很高，用下标直接找父子节点也很方便，所以堆是用数组实现的，每次排序的节点都会被移动数到数组的末尾，让一个新的数组形成一个新的堆继续。从大的角度来看，堆排序可以分为两部分，用无序数组构建堆，并在堆的基础上进行自上而下的排序。其中，为无序数组建堆的时间复杂度为O(n)。堆基排序每次取堆顶元素，然后将最后一个元素移到堆顶，调整堆。每次只需要O(logn)级别。时间复杂度，完成n次排序是O(nlogn)，但是我们每次只需要k次，所以完成k元素排序功能需要O(klogn)时间复杂度，整个时间复杂度是O(n+klogn)不会合并，因为它区别于上一个。我画了一张图帮助大家理解，做2次就得到Top2，做k次就得到TopK。实现代码为：classSolution{privatevoidswap(int[]arr,inti,intj){inttemp=arr[i];arr[i]=arr[j];arr[j]=temp;}//下移交换当前节点有效转化为堆（大根）publicvoidshiftDown(intarr[],intindex,intlen)//0号位置未使用{intleftchild=index*2+1;//leftchildintrightchild=index*2+2;//右孩子if(leftchild>=len)return;elseif(rightchildarr[index]&&arr[rightchild]>arr[leftchild])//右孩子在范围内，应该交换{swap(arr,index,rightchild);//交换节点值shiftDown(arr,rightchild,len);//可能对子节点的堆有影响，向下重构}elseif(arr[leftchild]>arr[index])//交换左孩子{swap(arr,index,leftchild);shiftDown(arr,leftchild,len);}}//创建数组入堆publicvoidcreatHeap(intarr[]){for(inti=arr.length/2;i>=0;i--){shiftDown(arr,i,arr.length);}}publicintfindKthLargest(intnums[],intk){//step1建堆creatHeap(nums);//step2建一个有k个值的堆，每次取栈顶元素把堆放到最后for(inti=0;iend)return;intleft=start;intright=end;intnumber=nums[start];while(left=nums[left]&&leftk){quickSort(nums,left+1,end,k);}else{quickSort(nums,start,left-1,k-num);}}}计数排序Extrachapter排序总有一些排序操作——线性排序，那你可能会问，桶排序可以吗？也可以，但是要看优化的取值范围。桶排序适用于数据均匀密集且出现次数较多的情况，而计数排序希望值可以更小。那么使用桶排序的具体核心思想是什么呢？先用计数排序统计每个数字出现的次数，然后从后往前添加一个新的数组并计算和。这种情况很适合数值巨大，分布范围不大的情况。本来不想写代码的，想一想，我就写三遍吧//libutton215//1<=k<=nums.length<=104//-104<=nums[i]<=104publicintfindKthLargest(intnums[],intk){intarr[]=newint[20001];intsum[]=newint[20001];for(intnum:nums){arr[num+10000]]++;}for(inti=20000-1;i>=0;i--){sum[i]+=sum[i+1]+arr[i];if(sum[i]>=k)returni-10000;}return0;}好结论啦，今天的TopK题就到这里了，相信下次遇到的时候你一定会搞定的。TopK问题并不难，只是对排序的巧妙运用。排序很重要，面试也会很频繁。在这里我就不隐瞒摊牌了，我会如何引导大家站在面试官的角度来谈TOPK题。狡猾的面试官：嗯，那我们就说说数据结构和算法，再说说排序吧。你应该接触过它吧？说出你最熟悉的三种排序方式，并说明具体的算法方法。谦卑我：bialabialabialabiala...
