😋 最大的 K 元素
!本篇文章过于久远，其中观点和内容可能已经不准确，请见谅!~
很常见的一个 Leet-Code 问题，取出无序数组的最大 K 个数，比如【前-k-个高频元素】【数组中的第k个最大元素】。
下面以【前-k-个高频元素】为例写下思考：
最容易想到的一个方法，选最大的，那就从大到小排序后截取前 K 个呗。
这个算法的复杂度主要是排序部分，快排的话平均可以有 O(nlog2n)，加上截取部分的复杂度
O(K)。这样的一个处理方式很简单，但是直觉上就可以认为不是很好的方法，因为大于 k 值的元素不需要比较排序，例如 k = 1 或者很小的值的情况，算法需要对整个数组进行没必要的排序。在此考量下，可以采用部分比较的方法来实现。
冒泡排序或者选择排序的思路，只进行比较前 K 个大数即可，复杂度是 K 次遍历，也就是
O(nK)，但是这个当 n >> k 的时候遍历 k 次整个序列有点不好。O(nK) 的复杂度与方法一 O(nlog2n) 复杂度相比，当 k 较小的时候比较占优，也就是在 k < log2n 的时候选择方法二，而且不涉及到数组元素的移动和赋值，所以性能相比更好些。
二分法技巧的应用，选择二分点将数组分割，但是不是按照下标的方式，而是选择值和大小比较的分割，同时也不需要真实的切分数组，只需要统计数量即可，比如：
// [4,1,2,5,3,8,6,7,9], 2// 二分点为中位数// 1,9 -> 5// [4,1,2,3] [5,6,7,9]// 右侧不小于 5 的有 4 个，左边界向右移动// 5,9 -> 7// [5,6] [7,9]// 右侧不小于 7 的有 2 个，满足 k == 2 的条件// 即可确认最大的 k 个元素为不小于 7 的数
这种方法就是利用二分方法逼近目标值，然后得到分割点。
这个方法虽然比较奇怪，但是复杂度上至少比方法二要好一些，而且不需要修改原数组，空间复杂度较小，而且是在 k 比较大的时候比上两个好些，复杂度可以看做是最大最小值二分逼近第 k 大的数，平均为 O(nlog2k)，不过因为二分法最坏可能是 O(nk2)。
PS: 从上面的运行代码中也能看到第一个例子时间比方法二要多，但是后面的例子的时间更少些，因为第一个场景上出现了最坏的情况。
这个方法如果用递归更好理解，复杂度上只是把迭代换成了递归：
想象拿着一个筐去草莓园自助采摘，筐里最多装 k 个草莓，总头到尾不回头的采摘，刚开始先把筐装满，然后后面每遇到一个比筐里都小的，就把筐里最小的悄摸的吃了，把新的装进筐里，到最后肯定是能拿到全部草莓的最大的 K 个。（如果是真事的话，草莓也全给人家吃完了）。
这样的一个很好的场景是只需要遍历一次全数组就完成了，在 n 很大，k 相对较小的时候更好些。
具体实现就是：
复杂度主要是主循环里面
appendBucket 的复杂度，而且是向 k 大小的已排序序列中插入一个值，复杂度是正常排序去除 n，也就是堆排序、快速排序、归并排序等的思路，可以算是 O(log2K)，所以总的复杂度是 O(nlog2K)。优点是仅需要全部元素的一次遍历。PS：上面的代码为了表示怎么找到最小值的插入排序的思路，最后复杂度是 O(nK)，如果把appendBucket换成最小堆做就能做到 O(log2K)
最小堆的方法是一个更好的插入新数据的方式，因为不需要遍历那么多元素，平均复杂度更好些（但是存在最坏情况）：
感谢您的阅读，本文由 Ubug 版权所有。如若转载，请注明出处：Ubug（https://ubug.io/blog/bigger-k）
