锐客网

  1. 首页 > it技术 > >

找出N个数中最小的k个数问题(复杂度O(N*logk))

【找出N个数中最小的k个数问题(复杂度O(N*logk))】这是一个经典的算法题，下面给出的算法都在给定的数组基础上进行，好处时不用分配新的空间，坏处是会破坏原有的数组，可以自己分配新的空间以避免对原有数组的破坏。
思路一 先直接排序，再取排序后数据的前k个数。
排序算法用最快的堆排序，复杂度也会达到O(N*logN).

void filterDown(int* disorder, int pos, int size){ int temppos=pos,temp=0; while(temppos2){ if(2*temppos+2disorder[2*temppos+2]){ if(disorder[temppos]=0; j--){ filterDown(disorder, j, size); } for(int j=size-1; j>0; j--){ temp=disorder[0]; disorder[0]=disorder[j]; disorder[j]=temp; filterDown(disorder,0,j); } } int _tmain(int argc, _TCHAR* argv[]) { const int size=200; const int maxnum = 10000; const int k=10; int* disorder=new int[size]; srand((unsigned) time(NULL)); for(int i=0; i){ disorder[i]=rand()%maxnum; } heapSort(disorder,size); for(int i=0; i

当k接近于N时，可以用这种算法。

思路二 先排序前k个数，对于后面N-k个数，依次进行插入。
时间复杂度为O(k*n)
void insertSort(int* disorder, int size){ int temp=0,i=0; for(int j=1; j){ temp=disorder[j]; for(i=j; i>0; i--){ if(temp=0; i--){ if(temp
当k很小时，可以用这种算法

思路三 对前k个数，建立最大堆，对于后面N-k个数，依次和最大堆的最大数比较，如果小于最大数，则替换最大数，并重新建立最大堆。
时间复杂度为O(N*logk)
void filterDown(int* disorder, int pos, int size){ int temppos=pos,temp=0; while(temppos2){ if(2*temppos+2disorder[2*temppos+2]){ if(disorder[temppos]=0; j--){ filterDown(disorder, j, k); } for(int j=k; j){ if(disorder[j]0; j--){ temp=disorder[0]; disorder[0]=disorder[j]; disorder[j]=temp; filterDown(disorder,0,j); } for(int i=0; i
当k和N都很大时，这种算法比前两种算法要快很多。
转载于:https://www.cnblogs.com/studynote/p/3404873.html

    推荐阅读


    上一篇：经验总结15--Paypal支付，測试sandbox

    下一篇：deepin|deepin 安装docker 以及常用命令