首页 > 代码库 > 寻找数列中第K大的数

寻找数列中第K大的数

版权所有 未经允许 请勿擅自商用 转载请指明出处

最早看到这个问题是在那本Mark写的数据结构与算法分析的书中引论部分,当时就是瞅瞅,到了最近,在实际应用中,我需要查找一些列的数中第k大的数时,我才重新回顾品味这个问题。现在,实际问题中,我还暂时没有解决问题,但是这段思考过程很有意思,在这里给大家品味下。

具体的问题有点复杂,在这里就不赘述了,暂且将这个问题形式化的描述如下:

给定一个有限无序数列记做{an},从这个数列中找出第k大的数。

输入:数列{an},k

输出:第k大的数

首先,有个最简单的办法就是利用桶排序以及哈希散列的思想,假设数列中最大数为max,最小数为min,那么首先做一个数组长度为max – min + 1,然后做散列函数为an – min,对于冲突的处理是计数,最后从后往前扫描一次整个新建的数组,即可得到第k大的数。这样看似可以在O(n)的复杂度内解决问题,是一个经典的空间换时间的办法,但是具体情况是,其实这个算法的时间复杂度是O( n * ( max – min ) )的,所以这个的时间复杂度完全取决于数组的最大与最小数的差。但是一般在实际的数据中,数列是很分散的,如果特别分散的话,完全有可能max – min 是远大于n的,那么这个效果就非常差了,同时,这个算法的应用存在限制条件,首先,它只能用于数列中全部是正整数的情况,对于我在实际中需要找的数列是浮点数毫无办法,或者说是没有有效的办法;其次,算法基于一个假设,已经知道数列最大最小值(虽然这样的值可以同时计算出来,并且时间复杂度为O(n))。

上述的这种解决办法,在《编程珠玑》一书的第一章节里面涉及过,这种桶排序的思想在其中用到了极致,采用的是位数组,并且要求排序数组中的数不存在重复的情况,然后一共需要最大数的位数,然后找到某个数,将对应的位置置为1,之后就只要扫描1就可以取得排序,用到上述问题中,就是扫到k个1就可以得到结果,这样的数据结构在C++和Java中都有提供,为bitset类,这是题外话。

我自己首先想到的办法是,根据得到的k,建立一个长度为k的数组(暂且称为k数组),然后依次读取数据,每次读取数据时,就依次比对k数组中各个元素,如果有比k数组中的数大,那么将其插入到对应的位置,同时对k数组,从当前位置做后移的操作,舍弃掉最后一个数,那么这样就保持了一个k个有序的数列,当处理数列扫描完成,那么k数组的最后一个数据就是我们需要的数据,想法比较简单,代码很快就完成了。

int find_k( int p[], int n, int k )

{

//k数组

int kList[ k ];

//k数组的初始化

for( int i = 0; i < k; i++ )

kList[ i ] = 0;



for( int i = 0; i < n; i++ )

{

//比对k数组中的数

for( int j = 0; j < k; j++ )

{

if( p[ i ] > kList[ j ] )

{

//后移操作

for( int l = k - 1; l > j; l-- )

kList[ l ] = kList[ l - 1 ];

//取代 

kList[ j ] = p[ i ]; 

break;

}//end if

}//end for j

}//end for i

return kList[ k -1 ];



}



这样做的时间复杂度是多少呢?我可是自认为是O(kn)的,可是仔细分析,首先忽略k数组初始化的处理,其时间复杂度是o( n * k *L),其中L是平均每趟做移动操作的次数,这个平均值是k/2,那么这个算法的时间复杂度是o( n * k2 ),这样就很差了,因为只有k比n开根号小,这样的算法才算是“不错”的。

经过自己上面的这番努力,我决定寻找前人的经验,查询到编程之美一书上有类似的问题,及其探讨,在书中,上述问题加强了,问题是寻找k个最大的数(读到这里,推荐去阅读下《编程之美——微软技术面试心得》一书的2.5小节),而解决这个问题的方法是从最开始的原始方法开始讨论展开的。得到k个最大数,首先做排序,然后取前k个即可,而用快排或者堆排序,这样的时间复杂度是o(N*logN),于是基于这样的时间复杂度为起点,开始逐步的优化。优化的原因是,要得到k个最大数,只需要前k个数有序,时间复杂度的优化,只能从去除对k个以后的数进行排序展开。

文中给出的第一个方法就是基于快排的优化,方法如下:首先随机在数列中找到一个数,作为轴值,将数列划分成Sa和Sb两个部分,其中Sa中存放大于或等于轴值的数,Sb存放小于轴值的数,划分完成后,有如下两种情况:

1.Sa元素小于等于k,那么k个最大数为Sa中所有数,以及Sb中最大的k-|Sa|个数

2.Sa元素大于等于k,那么需要找到Sa中最大的k个数

文中指出,这样的时间复杂度平均为O(N*logK),表示不是很了解,求高手指点这个是怎么计算的,基于这个我写出了第二个寻找第k大的数的代码:

int find_k( vector find, int k )

{



if( find.size() < k )

{

return 0;

}

int p = find.at(0);

//Sa 和 Sb数组

vector findA, findB;

//不将轴值放入左右两边数组

for( int i = 1; i < find.size(); i++ )

{

if( find.at( i ) >= p )

findA.push_back( find.at( i ) );

else

findB.push_back( find.at( i ) );

}//end for



if( findA.size() == ( k - 1 ) )

{

return p;

}//end if

else if( findA.size() > (k - 1) )

{

return find_k2( findA, k );

}//end if

else

{

return find_k2( findB, k - findA.size()) ;

}

}

//end find_k2



这段代码使用到了vector类,也可以采用list类或者数组直接实现,主要是要知道左右两边的有的数据的数量即可,当然上述的实现可能跟前面算法分析的时间复杂度会有区别,因为采用Vector要考虑到数组扩充花费的时间开销,这就是为了简便实现付出的代码,当然可以一开始指定Vector的长度就为数组的长度来降低实现的代价,同时感兴趣的,可以用数组实现上述函数。

提示我的问题在这个地方,之前我的时间复杂度过高,是由于本身我在更新的过程中一直在保持k个数的有序,其实这是没有意义的事情,毕竟我要的只是第k个数,所以我只要知道我那k个数组中,最小的那个数即可,也就是一直保存的k个数,可以是无序的,但是,一定要知道其中最小值,有一个最小值,并且整体不一定有序,这样的数据结构一下就想到了最小值堆,首先将堆的接口声明如下,有些用不到的操作就没有定义了:

class minHeap{

private:

int* Heap; //用于存放堆元素的数组

int size; //数组大小

int n; //堆中元素个数

void shiftdown( int ); //堆的下拉操作

public:

minHeap( int* Heap, int num, int max )

bool isLeaf( int pos ) const

int leftchild( int pos ) const

int rightchild( int pos ) const

int parent ( int pos ) const

bool insert( const int );

bool removeMin( int& );

int getMin(); 

};

//end class minHeap




因为对于保存的k个数,其中最小的数就是其第k大的数,因此采用最小值堆,对于堆需要操作的时候,是检查到数列中的数大于这个最小值,那么堆就要进行更新,要删除当前的最小值,并加入新值(就是淘汰最后面那个数)。而对于堆的操作无论是插入,还是删除时间复杂度都是O(logK)的,K为堆的大小。因此修改之前的算法,那么,时间复杂度近一步降低到了O( N*logK ),至此我优化的过程结束。再往《编程之美》这一节往下看,正好与其思想不谋而合,书中指出,这样的解决,还可以解决当需要查找的数列不能完全读入内存的情况。还是那句话,think it deeper, code it simple.


新浪博客地址:

http://blog.sina.com.cn/u/1822488043

寻找数列中第K大的数