找数组中给定下标区间内的第K小(大)元素

今晚看了下MIT的算法导论公开课,发现一道题很有意思,涉及到多种算法的实现,就记下来以后再回顾。

给定数组,给定区间,求第K小(大)小的数如何处理?。

    1、排序,快速排序。我们知道,快速排序平均所费时间为n*logn,从小到大排序这n个数,然后再遍历序列中后k个元素输出,即可,总的时间复杂度为O(n*logn+k)=O(n*logn)。

    2、排序,选择排序。用选择或交换排序,即遍历n个数,先把最先遍历到得k个数存入大小为k的数组之中,对这k个数,利用选择或交换排序,找到k个数中的最小数kmax(kmax设为k个元素的数组中最小元素),用时O(k)(你应该知道,插入或选择排序查找操作需要O(k)的时间),后再继续遍历后n-k个数,x与kmax比较:如果x<kmax,则x代替kmax,并再次重新找出k个元素的数组中最大元素kmax‘(多谢jiyeyuran 提醒修正);如果x<kmax,则不更新数组。这样,每次更新或不更新数组的所用的时间为O(k)或O(0),整趟下来,总的时间复杂度平均下来为:n*O(k)=O(n*k)。

    3、维护k个元素的最大堆,原理与上述第2个方案一致,即用容量为k的最大堆存储最先遍历到的k个数,并假设它们即是最小的k个数,建堆费时O(k),有k1<k2<…kmax(kmax设为最大堆中的最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x<kmax,则更新堆(用时logk),否则不更新堆。这样下来,总费时O(k+(n-k)*logk)=O(N*logK)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk(不然,就如上述思路2所述:直接用数组也可以找出最大的k个元素,用时O(n*k))。

    4、按编程之美上解法二的所述,类似快速排序的划分方法,N个数存储在数组S中,再从数组中随机选取一个数X,把数组划分为Sa和Sb俩部分,Sa<=X<=Sb,如果要查找的k个元素小于Sa的元素个数,则返回Sa中较小的k个元素,否则返回Sa中所有的元素+Sb中较小的k-|Sa|个元素。不断递归下去,把问题分解成更小的问题,平均时间复杂度为O(N)(编程之美所述的n*logk的复杂度有误,应为O(N),特此订正。

前面三种算法只要学过一点算法知识的人,基本上一眼就能看出算法复杂度。第四种算法的严格证明比较麻烦,先给个简单如下:

把数组中所有的数分为5个一堆,那么总共会有n/5堆,对于每堆我们可以很快的找到中位数(因为只有5个所以很容易嘛),之后调用当前算法找到这n/5个中位数的中位数,用这个数来做pivot,所以这个算法被叫做Median of Medians algorithm。

把中位数的中位数作为pivot的话,那么原数组中便会有3/5*1/2个也就是3/10个小于等于这个pivot的,同理会有3/10大于这个pivot的,所以最坏情况下,数组被分为30%,70%或者70%,30%的两部分。

T(n)<=T(n/5)+T(7/10*n)+O(n)<=c*n*(1+9/10+(9/10)^2….)
所以T(n)=O(n)

也就是最坏情况下是O(n)。

严格的证明请参考Mark Allen Weiss的数据结构与算法分析–c语言描述一书上,第10章,第10.2.3节,最近也在学习这本书。这本书除了对算法分析外,对C语言编程的帮助也是很大的。

下载地址:http://vdisk.weibo.com/s/b9dwq

文字传递灵感,思考铸就梦想

十一城人人      十一城新浪微博

发表评论

电子邮件地址不会被公开。 必填项已用*标注