topk问题：求最小或最大的k个数，求第k大或第k小的数

最近做了道算法题，题目大概意思如下：输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

题目看起来不难，但是想要比较用比较高效的算法对于我这种新手来说还是比较困难的。

1.我最开始想到的是用做k轮选择排序（其实就是求k次最小值），因为选择排序有个特点就是每次都会,确定一个最小值，这样我们的时间复杂度就位 o(n * k)。
2.其次我有想到直接使用快速排序，在取前k个数，这样复杂度为o(nlogn)

对比了一下1,2，在k < logn的时候，我们其实用方法1会比较好，在 k > logn的时候用方法2比较高效。

但是自我感觉了一下，觉得算法的复杂度还是有点高，因为我们只需要找到最小的前k个数，直接快速排序就显得有些多余了。
我想着尽量能将复杂度降到o(n),甚至log(n)。
让后想了很久也没想出来，最后从网上找到了一种比较高效的解法，它利用的是快排思想。
想要了解这种算法就要非常熟悉快排。
快排的思想就是：每次找一个基准值，将数组中的其他值与基准值比较，最后，小于基准值的落在基准值左边，大于基准值的落在基准值右边。这样一轮排序过后，其实基准值的位置就已经确定下来了，由于这里主要讲解topk问题，故快速排序不在这里过多阐述。

基于快排思想的算法代码如下：

 public int[] getLeastNumbers(int[] arr, int k

最后

以上就是留胡子月亮为你收集整理的topk问题：求最小或最大的k个数，求第k大或第k小的数的全部内容，希望文章能够帮你解决topk问题：求最小或最大的k个数，求第k大或第k小的数所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。