题目的主要信息:
- 先给出位候选人的名字,字符串表示
- 后续给出张票,票上是候选人的名字,统计每位候选人的票数
- 票里出现非候选人的名字则是属于不合法
- 输出按照输入的候选人的顺序排序
方法一:暴力查找
具体做法:
我们可以用一个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; //总票数减去合法票数就是非法票数
}
}
复杂度分析:
- 时间复杂度:,其中为候选人人数,为投票的总数,对于每张票都需要遍历所有候选人找到合适的候选人
- 空间复杂度:,记录候选人及票数的数组长度最多为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; //总票数减去合法票数就是非法票数
}
}
复杂度分析:
- 时间复杂度:,其中为候选人人数,为投票的总数,需要遍历输入所有候选人和投的票数,unordered_map的查找每次都是
- 空间复杂度:,记录候选人的哈希表最长为候选人人数