共计 4850 个字符，预计需要花费 13 分钟才能阅读完成。
前言
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] <= 104
public 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，转载请附上本文链接，原创不易，求个点赞关注，谢谢！
