共计 1848 个字符，预计需要花费 5 分钟才能阅读完成。
前言
明天给大家分享一个 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)因为和后面辨别一下就不合并了。