本文转载自微信公众号《桐人的技术分享》，作者kiritomoe。转载本文请联系桐人的技术分享公众号。把问题简单抽象一下就是今天的主题：在百万级无序长数组中，求第K大数。当然，要求是越早找到越好。一提到topK问题，很多人就会想到topK问题。无论是在算法领域还是工程领域，这个问题都被广泛讨论，在实际项目中很容易遇到类似的问题。正好借此机会总结成一篇文章。常见的topK问题及其变体：有10,000,000条记录，这些查询字符串的重复率比较高。如果去除重复，则不会超过3,000,000。查询字符串的重复率越高，用户查询的越多，即越受欢迎。请统计最流行的10个查询字符串，所需内存不能超过1GB。有10个文件，每个文件1GB，每个文件的每一行存储用户的查询，每个文件的查询可能会重复。按查询频率排序。有一个1GB大小的文件，里面每一行是一个word，一个word的大小不超过16字节，内存限制大小为1MB。返回100个最常用的单词。提取某天访问网站次数最多的IP。10亿个整数找出重复次数最多的100个整数。搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条。每个输入字符串不超过255B，内存占用仅为1GB。一千万个身份证号及其对应的数据，身份证号可能重复，找出出现次数最多的身份证号。传统topK问题说明：在海量数据中找到最大的topK数。注意，我这次提出的问题和传统的topK有点不同，传统的topK问题一般要求“topK最大的数”，而我现在遇到的是“第K大数”。差别不大，但可能对我们最终选择的解决方案产生很大的影响。下面我将介绍一些传统的TopK问题的解决方案。而且，按照我一贯的作风，肯定会有代码放出来的。如果你正在寻找“从海量无序数据中找出第K大数”这个问题的答案，相信你可以直接copy我的代码。方案一：排序法排序法是最容易想到的思路，复杂度为O(nlogn)。各种可以想象得到的排序算法层出不穷，比如快速排序、归并排序、插入排序、猴子排序……等等。然而，工程领域的方案选择往往不能仅以复杂度来评价算法：每种排序方案交换的数据量Extraspace应用量的平均复杂度，最差复杂度，不同数据量下的性能。这时候就会有人问，我应该如何选择合适的解决方案呢？哎，那我又要提那句话了，benchmarkeverything！虽然你肯定知道我最终没有选择用排序来解决第K大问题，但我还是想和你分享一些我的测试结果。在100w~1000w数据量级别的无序长数组中，JDK自带的Array.sort()比任何排序方案都要快。Array.sort的内部实现是timsort，它是一种优化的归并排序。单纯靠思考排序并不是最好的解决办法，因为在我提出的问题中，只需要找到第K大的数，但是排序方案已经动员了人去理顺整个数组，这是没有必要的。解法二：堆对于一般的topK问题，默认的K一般很小，所以一般的topK问题可以用堆来解决。堆有一个重要的性质：每个节点的值不大于其左右子节点的值，那么堆顶元素就是整个堆的最小值。JDK中的PriorityQueue实现了堆数据结构heap。通过指定比较器字段来表示小顶堆或大顶堆，默认是自然排序。SmallTopHeap解决TopK问题的思路：SmallTopHeap维护当前扫描的最大K个数，之后每次扫描的元素，如果大于堆顶，则放入入堆，然后将堆顶删除；依此类推，直到扫描完所有元素。Java实现第K大整数代码如下：|num>minQueue.peek())minQueue.offer(num);if(minQueue.size()>k)minQueue.poll();}returnminQueue.peek();}回到我遇到的问题，求第K个对于大数，这里不指定K的范围，所以在最坏的情况下，K==N/2，无论是维护topK的小顶堆还是维护top(N-K)的大顶堆，它需要占用O(N/2)内存，这对于大量数据来说似乎是一个非常大的开销。所以对于我比赛的场景，堆方案可以直接通过。堆方案适用于K较小的场景，维护前K个数非常方便。解决方案三：QuickSelectQuickSelect你可能没有听说过，但你一定听说过QuickSort（快速排序）。其实这两个算法的作者都是Hoare，思路很相似：选择一个参考元素pivot，将数组Partition（分区）分成两个子数组，抛出比pivot大的左边子数组，抛出比主元小的右子数组，然后递归拆分子数组。QuickSelect与QuickSort不同的是，它不拆分每个子数组，而是拆分目标子数组。其次，QuickSelect和QuickSort一样，是一个不稳定的算法；pivot的选择直接影响算法的好坏，最坏情况下的时间复杂度达到O(n2)。大学参加ACM的时候，第一次接触到这个算法。记得当时数据量刚刚卡住的QuickSort过不了，而QuickSelect可以过。QuickSelect的Java实现如下：(开始+结束)/2];while(left<=right){while(left<=right&&nums[left]>pivot){left++;}while(left<=right&&nums[right]
