当前位置:编程学习 > C/C++ >>

九度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++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,