PAT-B-1038-统计同成绩学生

本题要求读入 N 名学生的成绩，将获得某一给定分数的学生人数输出。

输入格式：

输入在第 1 行给出不超过 105 的正整数 N，即学生总人数。随后一行给出 N 名学生的百分制整数成绩，中间以空格分隔。最后一行给出要查询的分数个数 K（不超过 N 的正整数），随后是 K 个分数，中间以空格分隔。

输出格式：

在一行中按查询顺序给出得分等于指定分数的学生人数，中间以空格分隔，但行末不得有多余空格。

输入样例：

1
2
3

10
60 75 90 55 75 99 82 90 75 50
3 75 90 88

输出样例：

3 2 0

Code

//笨方法，时间复杂度为O(n^2)会超时
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(){
	vector<int> score;
	int n,temp;
	scanf("%d",&n);
    while(n--){
        scanf("%d",&temp);
        score.push_back(temp);
    }

    sort(score.begin(),score.end());
    int m,count;
    scanf("%d",&m);
    while(m--){
        count=0;
        int t;
        scanf("%d",&t);

        for(int i=0;i<score.size();i++){
            if(score[i]==t)
                count++;
            if(count>0&&score[i]!=t)
                break;
        }

        printf("%d",count);
        if(m!=0)
            printf(" ");
    }


	return 0;
}

//开辟数组来存储时间复杂度O(m)
#include <iostream>
using namespace std;

int main(){
	int score[101]={0};
	int n,temp;
	scanf("%d",&n);
    while(n--){
        scanf("%d",&temp);
        score[temp]++;
    }

    int m;
    scanf("%d",&m);
    while(m--){
        int t;
        scanf("%d",&t);
        printf("%d",score[t]);
        if(m!=0)
            printf(" ");
    }
	return 0;
}