Day7 洛谷P1138 第k小整数(桶排序)

题目

现有n个正整数，n≤10000，要求出这n个正整数中的第k个最小整数（相同大小的整数只计算一次），k≤1000，正整数均小于30000。

输入输出格式

输入格式：
第一行为n和k; 第二行开始为n个正整数的值，整数间用空格隔开。

输出格式：
第k个最小整数的值；若无解，则输出“NO RESULT”。

输入输出样例

输入样例#1：
10 3
1 3 3 7 2 5 1 2 4 6
输出样例#1：
3

答案

#include<stdio.h>
int main()
{
	int n,k;//代表一共有n个整数，要找第k小的数
	int a[30005]={0};//储存n个整数
	int b[30005]={0};//做桶
	int i,t;//角标,中间量 
	int cnt=0;//计数器
	scanf("%d %d",&n,&k);
	for (i=1;i<=n;i++)
	 {
	 	scanf("%d",&a[i]);
	 	t=a[i];//将该整数赋给中间量t，便于在桶堆中记录
	 	b[t]=1;//b数组中相应的位置赋1
	 }
	for (i=1;i<=30005;i++)//开始遍历处理桶堆
	{
		if (b[i])//若b中相应位置不为0 证明输入的n的整数中有这个数
		{
			cnt++;
		}
		if (cnt==k)
		{
			printf("%d",i);
			return 0;
		}
	} 
	if (cnt<k)
	{
		printf("NO RESULT");
	}
	return 0;
}

补充资料：
桶排序相关介绍（来自《啊哈算法》）