由于对一个有序的数组而言,能非常容易地找到数组中第k小的数,因此,可以通过对数组进行排序的方法来找出第k小的数。同时,由于只要求第k小的数,因此,没有必要对数组进行完全排序,只需要对数组进行局部排序就可以了。下面分别介绍这几种不同的实现方法。
方法一:排序法
最简单的方法就是首先对数组进行排序,在排序后的数组中,下标为k-1的值就是第k小的数。例如:对数组[4,0,1,0,2,3]进行排序后的序列变为[0,0,1,2,3,4],第3小的数就是排序后数组中下标为2对应的数:1。由于最高效的排序算法(例如快速排序)的平均时间复杂度为O(Nlog2N),因此,此时该方法的平均时间复杂度为O(Nlog2N),其中,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)划分为三部分:
(0), (0), (1)
此时i=1, low=0; (i-1=1)<(k-1=2),接下来需要在(1)中找第k-(i-low)-1=1小的元素即可。显然,(1)中第1小的元素就是1。
实现代码如下:
"""
方法功能: 在数组array中找出第k小的值
输入参数: array为整数数组, low为数组起始下标, high为数组右边界的下标, k为整数
返回值: 数组中第k小的值
"""
def findSmallK(array,low,high,k):
i=low
j=high
splitElem=array[i]
#把小于等于splitElem的数放到数组中splitElem的左边, 大于splitElem的值放到右边
while i<j:
while i<j and array[j]>=splitElem:
j-=1
if i<j:
array[i]=array[j]
i+=1
while i<j and array[i]<=splitElem:
i+=1
if i<j:
array[j]=array[i]
j-=1
array[i]=splitElem
#splitElem在子数组array[low~high]中下标的偏移量
subArrayIndex=i-low
#splitElem在array[low~high]所在的位置恰好为k-1, 那么它就是第k小的元素
if subArrayIndex==k-1:
return array[i]
# splitElem在array [low~high]所在的位置大于k-1, 那么只需在array[low~i-1]中找第k小的元素
elif subArrayIndex>k-1:
return findSmallK(array, low, i-1, k)
#array[i+1~high]中找第k-i+low-1小的元素
else:
return findSmallK(array, i+1, high, k-(i-low)-1)
if __name__=="__main__":
k=3
array=[4,0,1,0,2,3]
print "第"+str(k)+"小的值为:"+str(findSmallK(array,0,len(array)-1,k))
程序的运行结果为:
第3小的值为:1
算法性能分析:
快速排序的平均时间复杂度为O(Nlog2N)。快速排序需要对划分后的所有子数组继续排序处理,而本方法只需要取划分后的其中一个子数组进行处理即可,因此,平均时间复杂度肯定小于O(Nlog2N)。由此可以看出,这种方法的效率要高于方法一。但是这种方法也有缺点:它改变了数组中数据原来的顺序。当然可以申请额外的N(其中,N为数组的长度)个空间来解决这个问题,但是这样做会增加算法的空间复杂度,所以,通常做法是根据实际情况选取合适的方法。
[考点] 如何找出数组中第k小的数