九度OJ 题目1371:最小的K个数
题目描述:输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
输入:
每个测试案例包括2行:
第一行为2个整数n,k(1<=n,k<=200000),表示数组的长度。
第二行包含n个整数,表示这n个数,数组中的数的范围是[0,1000 000 000]。
输出:
对应每个测试案例,输出最小的k个数,并按从小到大顺序打印。
样例输入:
8 44 5 1 6 2 7 3 8
样例输出:
1 2 3 4
思路:
面对如此规模的n,k采用一般方法肯定会超时的,我们维护一个K个元素的最大堆,(前K个元素初始化建堆),然后每次读入一个元素,就和堆顶元素相比较
如果该元素比堆顶元素大,那么跳过,否则更新堆顶元素,并调整堆,这样一遍之后,我们得到了最小的K个元素构成的最大堆,再排序即可。
代码:
#include<iostream> #include<algorithm> #include<cstdlib> #include<cstdio> using namespace std; const int MAX=200001; int min_k[MAX]; void heap_adj(int *a,int i,int len) { int index=i*2; int p=2*i,q=p+1; if(q<=len && a[p]<a[q]) index=q; if(index<=len && a[i]<a[index]) { swap(a[i],a[index]); heap_adj(a,index,len); } } void makeheap(int *a,int len) { for(int i=len/2;i>=1;i--) heap_adj(a,i,len); } int main() { int n,k; while(cin>>n>>k) { for(int i=1;i<=k;i++) scanf("%d",&min_k[i]); makeheap(min_k,k); for(int i=k+1;i<=n;i++) { int tmp; scanf("%d",&tmp); if(tmp<min_k[1]){ min_k[1]=tmp; heap_adj(min_k,1,k); } } sort(min_k+1,min_k+1+k); for(int i=1;i<k;i++) cout<<min_k[i]<<" "; cout<<min_k[k]<<endl; } return 0; }
补充:软件开发 , C++ ,