第k小数(桶排序)
标签：tar its pre ref har style code std color
https://ac.nowcoder.com/acm/contest/5773/A
给一个数列，求第k小的数。
一开始想的是集合、优先队列，自动排好序的容器。交上去两个都t了。
换一种思路，用个桶排序，每次遇到一个数加1，从小到大扫一遍，每遇到数列里的数计数加一，等于k时输出。
#includeusing namespace std;
const int maxn=5e6;
inline int read(){
int x = 0, f = 1;
char ch = getchar();
while(ch ‘0‘ || ch > ‘9‘){
if (ch == ‘-‘)
f = -1;
ch = getchar();
}
while(ch >= ‘0‘ && ch ‘9‘){
x = (x1) + (x3) + (ch^48);
ch = getchar();
}
return x * f;
}
int s[maxn+5];
int main(){
int m,n,k,t;
t=read();
for(int i=0;i){
n=read();
k=read();
fill(s,s+maxn,0);
for(int j=0;j){
m=read();
s[m]++;
}
int cnt=0;
for(int o=1;o){
while(s[o]){
s[o]--;cnt++;
if(cnt==k){coutbreak;}
}
}
}
return 0;
第k小数(桶排序)
标签：tar its pre ref har style code std color
原文地址：https://www.cnblogs.com/mohari/p/12961032.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
第k小数(桶排序)
文章链接：http://soscw.com/index.php/essay/41240.html
评论