题目的主要信息:

  • 先给出mm位候选人的名字,字符串表示
  • 后续给出nn张票,票上是候选人的名字,统计每位候选人的票数
  • 票里出现非候选人的名字则是属于不合法
  • 输出按照输入的候选人的顺序排序

方法一:暴力查找

具体做法:

我们可以用一个pair型的vector数组来存储这个每个候选人及其票数,输入候选人姓名的时候就初始化票数为0. 然后根据输入的票,遍历查找数组中候选人的名字刚好等于输入的票,再给那个人票数增加1。 最后按照顺序输出数组两部分即可,同时要统计输出的票数有多少,总票数减去输出的票数就是不合法的票数。

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        vector<pair<string, int> > name(n);
        string s;
        for(int i = 0; i < n; i++){ 
            cin >> s;
            name[i] = make_pair(s, 0); //记录候选人的名字,初始票数为0
        }
        cin >> n;
        for(int i = 0; i < n; i++){ 
            cin >> s;
            for(int i = 0; i < name.size(); i++) //只查找到有这个候选人的再计票
                if(s == name[i].first)
                    name[i].second++;
        }
        int valid = 0; //统计合法票数
        for(int i = 0; i < name.size(); i++){ //遍历候选人的名字,输出其票数
            cout << name[i].first << " : " << name[i].second << endl;
            valid += name[i].second;
        }
        cout << "Invalid : " << n - valid << endl; //总票数减去合法票数就是非法票数
    }
}

复杂度分析:

  • 时间复杂度:O(nm)O(nm),其中mm为候选人人数,nn为投票的总数,对于每张票都需要遍历所有候选人找到合适的候选人
  • 空间复杂度:O(m)O(m),记录候选人及票数的数组长度最多为m$

方法二:哈希表

具体做法:

可以用哈希表改进上述查找,一位字符串数组记录所有的胡候选人姓名,同时它的作用是记住输入的顺序。然后我们用一个哈希表的key值记住这些候选人的名字,value值表示票数,初始化为0.

然后遍历所有输入的票数,先查找哈希表中是否有这个人,只对哈希表中存在这个候选人的情况增加票数,否则就是不合法的票。

最后遍历数组的每个字符串,在哈希表中找到字符串对应的value值输出,同时累加票数,总票数减去输出的票数就是不合法的票数。

alt

#include<iostream>
#include<string>
#include<vector>
#include<unordered_map>
using namespace std;

int main(){
    int n;
    while(cin >> n){
        unordered_map<string, int> mp;
        vector<string> name(n);
        string s;
        for(int i = 0; i < n; i++){ 
            cin >> s;
            mp[s] = 0; //在map中记录候选人,设置票数为0
            name[i] = s; //记录候选人的名字
        }
        cin >> n;
        for(int i = 0; i < n; i++){ 
            cin >> s;
            if(mp.find(s) != mp.end()) //只对map中有的候选人计票
                mp[s]++;
        }
        int valid = 0; //统计合法票数
        for(int i = 0; i < name.size(); i++){ //遍历候选人的名字,输出其票数
            cout << name[i] << " : " << mp[name[i]] << endl;
            valid += mp[name[i]];
        }
        cout << "Invalid : " << n - valid << endl; //总票数减去合法票数就是非法票数
    }
}

复杂度分析:

  • 时间复杂度:O(n+m)O(n+m),其中mm为候选人人数,nn为投票的总数,需要遍历输入所有候选人和投的票数,unordered_map的查找每次都是O(1)O(1)
  • 空间复杂度:O(m)O(m),记录候选人的哈希表最长为候选人人数