题目的主要信息：

• 先给出$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值输出，同时累加票数，总票数减去输出的票数就是不合法的票数。

#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)$，记录候选人的哈希表最长为候选人人数