Interview Practice 05 - K Smallest Elements in List

Question

输入n个整数,输出其中最小的k个。
例如输入1,2,3,4,5,6,7和8这8个数字,
则最小的4个数字为1,2,3和4。

Sample Code

[expand title=”Sample Code in C++” tag=”h4″]

include using namespace std; class MinK { private: int array; int size; void shiftDown(int ret,int pos,int length) { int t=ret[pos]; for(int s=2pos+1;s<=length;s=2s+1) { if(s<length&&ret[s]<ret[s+1]) ++s; if(t<ret[s]) { ret[pos]=ret[s]; pos=s; } else break; } ret[pos]=t; } public: MinK(int arr,int si): array(arr), size(si) {} bool kmin(int k,int& ret) { if(k>size) { ret=NULL; return false; } else { ret=new int[k--]; int i; for(i=0;i<=k;++i) ret[i] = array[i]; for(int j=(k-1)/2;j>=0;--j) shiftDown(ret,j,k); for(;i<size;++i) { if(array[i]<ret[0]) { ret[0]=array[i]; shiftDown(ret,0,k); } } return true; } } void remove(int*& ret){ delete[] ret; ret=NULL; } }; int main() { int array[]={1,2,3,4,5,6,7,8}; MinK mink(array,sizeof(array)/sizeof(array[0])); int *ret; int k=4; if(mink.kmin(k,ret)) { for(int i=0;i<k;++i) cout<<ret[i]<<endl; mink.remove(ret); } return 0; }

[/expand]

Show Comments