洛谷P1271 【深基9.例1】选举学生会

【深基9.例1】选举学生会

题目描述

学校正在选举学生会成员，有 $n(n\le 999)$ 名候选人，每名候选人编号分别从 1 到 $n$，现在收集到了 $m(m<=2000000)$ 张选票，每张选票都写了一个候选人编号。现在想把这些堆积如山的选票按照投票数字从小到大排序。

输入格式

输入 $n$ 和 $m$ 以及 $m$ 个选票上的数字。

输出格式

求出排序后的选票编号。

样例 #1

样例输入 #1

5 10
2 5 2 2 5 2 2 2 1 2
1
2

样例输出 #1

1 2 2 2 2 2 2 2 5 5
1

思路：如果我们按照以往先排序再输出，时间复杂度会很高，随着你的候选人的增多，时间复杂度也是增高的很快，这个时候我们可以思考，因为候选人的的编号就是数字，那么我们可以只构建一个数组，这个数组的下标就对应的候选人编号，每输入一张选票，我就判断这张选票是投给谁的，那我就在候选人数组上+1；直至把投票读完，读完后，我从这个候选人数组第一个候选人输出，只要这个候选人有x张选票，我就输出x次，以此类推就直接输出结束，该程序的时间复杂度为max（O（n），O（m）），空间复杂度为1000；该程序我认为鄙人想出的方法虽然笨重，但是已达到挺优的，下面附上代码，如有新想法，欢迎q我，谢谢大家！
代码如下（编译器dev，语言是C语言）：

#include
int n,m;
int a[1000];
int i,j,temp;
int main(){
    scanf("%d %d",&n,&m);
    for(i = 1;i<=m;i++){
        scanf("%d",&temp);
        a[temp] ++;
    }
    for(i = 1;i<1000;i++){
        if(a[i] == 0){
            continue;
        }
        for(j = 1;j<=a[i];j++){
            printf("%d ",i);
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20