求最小的K个数
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
解题方案 方法一排序（冒泡/选择）
思路
1，冒泡排序是每执行一次，就会确定最终位置，执行K次后，就可以得到结果，时间复杂度为O(n * k),当k<<n时，O(n * k)的性能会比O(N*logN)好。
2，选择排序每执行依次，就会通过确定一个最大的或最小的放在一端，通过选择排序，执行K次就可以得到最大的K个数了。时间复杂度时O(N * K)。
代码实现
方法二分治-快速排序
思路
1，快速排序的核心是分治思想，先通过分治partition把序列分为两个部分，再将两个部分进行再次递归；
2，利用分治思想，即划分操作partition，根据主元素pivot调整序列，比pivot大的放在左端，比pivot小的放在右端，这样确定主元素pivot的位置pivotIndex，如果pivotIndex刚好是k-1，那么前k-1位置的数就是前k大的元素，即我们要求的top K。
时间复杂度: O(n)
代码实现
方法三利用堆
思路
1，构建一个最大堆
2，遍历原数组，元素入队，当堆的大小为K时，只需要将堆顶元素于下一个元素比较，如果大于堆顶元素，则将堆顶元素删除，将该元素插入堆中，直到遍历完所有元素
3，将queue存储的K个数出队
时间复杂度：为O(N*logK)
代码实现
到此这篇关于Java深入分析与解决Top-K问题的文章就介绍到这了,更多相关Java Top-K内容请搜索七叶笔记以前的文章或继续浏览下面的相关文章希望大家以后多多支持七叶笔记！
