首页 > 代码库 > 寻找数列中第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数组的最后一个数据就是我们需要的数据,想法比较简单,代码很快就完成了。
这样做的时间复杂度是多少呢?我可是自认为是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大的数的代码:
这段代码使用到了vector类,也可以采用list类或者数组直接实现,主要是要知道左右两边的有的数据的数量即可,当然上述的实现可能跟前面算法分析的时间复杂度会有区别,因为采用Vector要考虑到数组扩充花费的时间开销,这就是为了简便实现付出的代码,当然可以一开始指定Vector的长度就为数组的长度来降低实现的代价,同时感兴趣的,可以用数组实现上述函数。
提示我的问题在这个地方,之前我的时间复杂度过高,是由于本身我在更新的过程中一直在保持k个数的有序,其实这是没有意义的事情,毕竟我要的只是第k个数,所以我只要知道我那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大的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。