排序-签到题I
题目
https://ac.nowcoder.com/acm/problem/25519
code
#include <stdio.h>
int main()
{
int n,k,i,sum=0;
scanf("%d%d\n",&n,&k);
int a[n];
int b[100001]={0};
for(i=0;i<n;i++)
{
scanf("%d",&a[i]);
b[a[i]]++;
}
for(i=0;i<100001;i++)
{
sum+=b[i];
if(sum>=k)
{
printf("%d",i);
break;
}
}
}
解题思路
用另外一组数组b，来计算a数组中数出现的次数，同时a数组中数字的大小，也决定了在b数组中的位置；而后通过sum将b数组相加，即将a数组出现的次数相加，再将sum与k比较，大于等于k则表示第k小的数字，输出i（在b数组中，i数表示第i位数，在a数组中表示，a[i]的大小）。
妙
利用b数组，表示a[i]出现的次数，同时决定了a[i]在b中的位置。
滴滴公司福利 648人发布
查看13道真题和解析