前言

hello，大家好，我是bigsai哥哥，好久不见，甚是惦记哇！

明天给大家分享一个TOPK问题，不过我这里不思考特地大分布式的解决方案，一般的一道算法题。

首先搞清楚，什么是topK问题？

topK问题，就是找出序列中前k大(或小)的数，topK问题和第K大(或小)的解题思路其实大抵统一的。

TopK问题是一个十分经典的问题，在口试和面试中呈现的频率都十分十分高(从不说实话)。上面，从小小白的出发点,认为topK是求前K大的问题，一起意识下TopK吧！

以后，在求TopK和第K大问题解法差不多，这里就用力扣215数组的第k个大元素 作为解答的题演示啦。学习topk之前，这篇程序员必知必会的十大排序肯定要会。

排序法

找到TopK，并且排序TopK

啥，你想要我找到TopK？不光光TopK，你想要多少个，我给你多少个，并且还给你排序给排好，啥排序我最相熟呢？

如果你想到冒泡排序O(n^2)那你就粗心了啊。

如果应用O(n^2)级别的排序算法，那也是要优化的，其中冒泡排序和简略抉择排序，每一趟都能程序确定一个最大(最小)的值，所以不须要把所有的数据都排序进去，只须要执行K次就行啦，所以这种算法的工夫复杂度也是O(nk)。

这里给大家回顾一下冒泡排序和简略抉择排序区别：

冒泡排序和简略抉择排序都是多趟，每趟都能确定一个最大或者最小，区别就是冒泡在枚举过程中只和本人前面比拟，如果比前面大那么就替换；而简略抉择是每次标记一个最大或者最小的数和地位，而后用这一趟的最初一个地位数和它替换(每一趟确定一个数枚举范畴都缓缓变小)。

上面用一张图示意过程：

这里把code也给大家提供一下，简略抉择下面图给的是每次选最小，实现的时候每次选最大就能够了。

//替换数组中两地位元素private void swap(int[] arr, int i, int j) {  int temp = arr[i];  arr[i] = arr[j];  arr[j] = temp;}//冒泡排序实现public int findKthLargest1(int[] nums, int k) {  for(int i=nums.length-1;i>=nums.length-k;i--)//这里也只是k次  {    for(int j=0;j<i;j++)    {      if(nums[j]>nums[j+1])//和右侧街坊比拟      {        swap(nums,j,j+1);      }    }  }  return nums[nums.length-k];}//简略抉择实现public int findKthLargest2(int[] nums, int k) {  for (int i = 0; i < k; i++) {//这里只须要K次    int max = i; // 最小地位    for (int j = i + 1; j < nums.length; j++) {      if (nums[j] > nums[max]) {        max = j; // 更换最小地位      }    }    if (max != i) {      swap(nums, i, max); // 与第i个地位进行替换    }  }  return nums[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)因为和后面辨别一下就不合并了。

画了一张图帮忙大家了解，进行两次就取得Top2，进行k次就取得TopK了。

实现代码为：

class Solution {    private void swap(int[] arr, int i, int j) {        int temp = arr[i];        arr[i] = arr[j];        arr[j] = temp;    }    //下移替换 把以后节点无效变换成一个堆(大根)    public void shiftDown(int arr[],int index,int len)//0 号地位不必    {        int leftchild=index*2+1;//左孩子        int rightchild=index*2+2;//右孩子        if(leftchild>=len)            return;        else if(rightchild<len&&arr[rightchild]>arr[index]&&arr[rightchild]>arr[leftchild])//右孩子在范畴内并且应该替换        {            swap(arr, index, rightchild);//替换节点值            shiftDown(arr, rightchild, len);//可能会对孩子节点的堆有影响，向下重构        }        else if(arr[leftchild]>arr[index])//替换左孩子        {            swap(arr, index, leftchild);            shiftDown(arr, leftchild, len);        }    }    //将数组创立成堆    public void creatHeap(int arr[])    {        for(int i=arr.length/2;i>=0;i--)        {            shiftDown(arr, i,arr.length);        }    }    public int findKthLargest(int nums[],int k)    {        //step1建堆        creatHeap(nums);        //step2 进行k次取值建堆，每次取堆顶元素放到开端        for(int i=0;i<k;i++)        {            int team=nums[0];            nums[0]=nums[nums.length-1-i];//删除堆顶元素，将开端元素放到堆顶            nums[nums.length-1-i]=team;            shiftDown(nums, 0, nums.length-i-1);//将这个堆调整为非法的大根堆，留神(逻辑上的)长度有变动        }        return nums[nums.length-k];    }}

基于快排优化

下面堆排序都能优化，那么快排呢？

快排当然能啊，这么牛的事件怎么能少得了我快排呢？

这部分须要堆快排有肯定理解和意识，后面很久前写过：图解手撕冒泡和快排 (前面待优化)，快排的核心思想就是：分治 ，每次确定一个数字的地位，而后将数字分成两个局部，左侧比它小，右侧比它大，而后递归调用这个过程。每次调整的工夫复杂度为O(n),均匀次数为logn次，所以均匀工夫复杂度为O(nlogn)。

然而这个和求TopK有什么关系呢？

咱们求TopK，其实就是求比指标数字大的K个，咱们随机选一个数字例如下面的5，5的左侧有4个，右侧有4个，可能会呈现上面几种状况了：

① 如果k-1等于5右侧数量，那么阐明两头这个5就是第K个，它和它的右侧都是TopK。

②如果k-1小于5右侧数的数量 ，那么阐明TopK全在5的右侧，那么能够间接压缩空间成右侧持续递归调用同样办法查找。

③ 如果k-1大于5右侧的数量，那么阐明右侧和5全副在TopK中，而后左侧还有(k-包含5右侧数总数)，此时搜查范畴压缩，k也压缩。举个例子，如果k=7 那么5和5右侧曾经占了5个数字肯定在Top7中，咱们只须要在5左侧找到Top2就行啦。

这样一来每次数值都会被压缩，这里因为快排不是齐全递归，工夫复杂度不是O(nlogn)而是O(n)级别(具体的能够找一些网上证实)，然而测试样例有些极其代码比方给你跟你有序1 2 3 4 5 6…… 找Top1 就呈现比拟极其的状况。所以具体时候会用一个随机数和第一个替换一下避免非凡样例(仅仅为了刷题用的),当然我这里为了就不加随机替换的啦，并且如果这里要失去的TopK是未排序的。

具体逻辑能够看下实现代码为：

class Solution {    public int findKthLargest(int[] nums, int k) {        quickSort(nums,0,nums.length-1,k);        return nums[nums.length-k];    }    private void quickSort(int[] nums,int start,int end,int k) {        if(start>end)            return;        int left=start;        int right=end;        int number=nums[start];        while (left<right){            while (number<=nums[right]&&left<right){                right--;            }            nums[left]=nums[right];            while (number>=nums[left]&&left<right){                left++;            }            nums[right]=nums[left];        }        nums[left]=number;        int num=end-left+1;        if(num==k)//找到k就终止            return;        if(num>k){            quickSort(nums,left+1,end,k);        }else {            quickSort(nums,start,left-1,k-num);        }    }}

计数排序番外篇

排序总有一些骚操作的排序—线性排序，那么你可能会问桶类排序能够嘛？

也能够啦，不过要看数值范畴进行优化，桶类排序适宜数据平均密集呈现次数比拟多的状况，而计数排序更是心愿数值可能小一点。

那么利用桶类排序的具体核心思想是怎么样的呢？

先用计数排序统计各个数字呈现次数，而后将新开一个数组从后往前叠加求和计算。

这种状况非常适合数值巨量并且散布范畴不大的状况。

代码原本不想写了，然而念在你会给我三连我写一下吧

//力扣215//1 <= k <= nums.length <= 104//-104 <= nums[i] <= 104public int findKthLargest(int nums[],int k){  int arr[]=new int[20001];  int sum[]=new int[20001];  for(int num:nums){    arr[num+10000]++;  }  for(int i=20000-1;i>=0;i--){    sum[i]+=sum[i+1]+arr[i];    if(sum[i]>=k)      return i-10000;  }  return 0;}

结语

好啦，明天的TopK问题就到这里啦，置信你下次遇到必定会拿捏它。

TopK问题不难，就是奇妙利用排序而已。排序是十分重要的，面试会十分高频。

这里我就不藏着掖着摊牌了，以面试官的角度会怎么疏导你说TOPK问题。

刁滑的面试官：

嗯，咱们来聊聊数据结构与算法，来讲讲排序吧，你应该接触过吧？讲出你最相熟的三种排序形式，并解说一下其中具体算法形式。

低微的我：

bia la bia la bia la bia la……

如果你提到快排，桶排序说不定就让你用这个排序实现一下TopK问题，其余排序也可能，所以把握好十大排序是十分必要的！

首发公众号：bigsai ，转载请附上本文链接，原创不易，求个点赞关注，谢谢！