Kotlin程序员面试：找数组中第k小的数

【出自HW面试题】

难度系数：★★★★☆ 被考察系数：★★★★☆

题目描述：

给定一个整数数组，如何快速地求出该数组中第k小的数。假如数组为{4，0，1，0，2，3}，那么第3小的元素是1。

分析与解答：

由于对一个有序的数组而言，能非常容易地找到数组中第k小的数，因此，可以通过对数组进行排序的方法来找出第k小的数。同时，由于只要求第k小的数，因此，没有必要对数组进行完全排序，只需要对数组进行局部排序就可以了。下面分别介绍这几种不同的实现方法。

方法一：排序法

最简单的方法就是首先对数组进行排序，在排序后的数组中，下标为k-1的值就是第k小的数。例如：对数组{4，0，1，0，2，3}进行排序后的序列变为{0，0，1，2，3，4}，第3小的数就是排序后数组中下标为2对应的数：1。由于最高效的排序算法（例如快速排序）的平均时间复杂度为O（Nlog₂^N），因此，此时该方法的平均时间复杂度为O（Nlog₂^N），其中，N为数组的长度。

方法二：部分排序法

由于只需要找出第k小的数，因此，没必要对数组中所有的元素进行排序，可以采用部分排序的方法。具体思路为：通过对选择排序进行改造，第一次遍历从数组中找出最小的数，第二次遍历从剩下的数中找出最小的数（在整个数组中是第二小的数），第k次遍历就可以从N-k+1（N为数组的长度）个数中找出最小的数（在整个数组中是第k小的）。这种方法的时间复杂度为O（n*k）。当然也可以采用堆排序进行k趟排序找出第k小的值。

方法三：快速排序方法

快速排序的基本思想是：将数组array[low…high]中某一个元素（取第一个元素）作为划分依据，然后把数组划分为三部分：（1）array[low…i-1]（所有的元素的值都小于或等于array[i]）、（2）array[i]、（3）array[i+1…high]（所有的元素的值都大于array[i]）。在此基础上可以用下面的方法求出第k小的元素：

（1）如果i-low==k-1，说明array[i]就是第k小的元素，那么直接返回array[i]。

（2）如果i-low＞k-1，说明第k小的元素肯定在array[low…i-1]中，那么只需要递归地在array[low…i-1]中找第k小的元素即可。

（3）如果i-low＜k-1，说明第k小的元素肯定在array[i+1…high]中，那么只需要递归地在array[i+1…high]中找第k-（i-low）-1小的元素即可。

对于数组{4，0，1，0，2，3}，第一次划分后，划分为下面三部分：

{3，0，1，0，2}，{4}，{}

接下来需要在{3，0，1，0，2}中找第3小的元素，把{3，0，1，0，2}划分为三部分：

{2，0，1，0}，{3}，{}

接下来需要在{2，0，1，0}中找第3小的元素，把{2，0，1，0}划分为三部分：

{0，0，1}，{2}，{}

接下来需要在{0，0，1}中找第3小的元素，把{0，0，1}划分为三部分：(www.xing528.com)

{0}，{0}，{1}

此时i=1，low=0；（i-1=1）＜（k-1=2），接下来需要在{1}中找第k-（i-low）-1=1小的元素即可。显然，{1}中第1小的元素就是1。

实现代码如下：

程序的运行结果如下：

第3小的值为：1

算法性能分析：

快速排序的平均时间复杂度为O（Nlog₂^N）。快速排序需要对划分后的所有子数组继续排序处理，而本方法只需要取划分后的其中一个子数组进行处理即可，因此，平均时间复杂度肯定小于O（Nlog₂^N）。由此可以看出，这种方法的效率要高于方法一。但是这种方法也有缺点：它改变了数组中数据原来的顺序。当然可以申请额外的N（其中，N为数组的长度）个空间来解决这个问题，但是这样做会增加算法的空间复杂度，所以，通常做法是根据实际情况选取合适的方法。

引申：在O（N）时间复杂度内查找数组中前三名

分析与解答：

这道题可以转换为在数组中找出前k大的值（例如，k=3）。

如果没有时间复杂度的要求，可以首先对整个数组进行排序，然后根据数组下标就可以非常容易地找出最大的三个数，即前三名。由于这种方法的效率高低取决于排序算法的效率高低，因此，这种方法在最好的情况下时间复杂度都为O（NlogN）。

通过分析发现，最大的三个数比数组中其他的数都大。因此，可以采用类似求最大值的方法来求前三名，具体实现思路为：初始化前三名（r1：第一名，r2：第二名，r3：第三名）为最小的整数。然后开始遍历数组：

1）如果当前值tmp大于r1：r3=r2，r2=r1，r1=tmp。

2）如果当前值tmp大于r2且不等于r1：r3=r2，r2=tmp。

3）如果当前值tmp大于r3且不等于r2：r3=tmp。

实现代码如下：

程序的运行结果如下：

前三名分别为7，6，5

算法性能分析：

这种方法虽然能够在O（N）的时间复杂度求出前三名，但是当k取值很大的时候，比如求前10名，这种方法就不是很好了。比较经典的方法就是维护一个大小为k的堆来保存最大的k个数，具体思路是：维护一个大小为k的小顶堆用来存储最大的k个数，堆顶保存了最小值，每次遍历一个数m，如果m比堆顶元素小，那么说明m肯定不是最大的k个数，因此，不需要调整堆，如果m比堆顶元素大，则用这个数替换堆顶元素，替换后重新调整堆为小顶堆。这种方法的时间复杂度为O（N*logk）。这种方法适用于数据量大的情况。