前言
明天给大家分享一个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)因为和后面辨别一下就不合并了。