排序-签到题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中的位置。