A50539.未出现的人 题解

可以想到，对于 $n$ 个人中的每一个，$O(m)$ 遍历查找是否在 $m$ 个出席者中，这样是 $O(nm)$ 的，可以通过本题。

当然，也有更好的做法，比如字符串哈希，可以做到线性，这里我使用的是又快又好写的 set。把 $m$ 个出席者加入到 set 中，再判断 $n$ 个人是否在 set 里，如果不在则输出。

时间复杂度：$O((n+m) \log m)$.

空间复杂度：$O(n+m)$.

Code:

#include<bits/stdc++.h>
using namespace std;
int n,m,ans;
string s;
string a[105];
set<string> sets;
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<=m;i++){
        cin>>s;
        sets.insert(s);
    }
    for(int i=1;i<=n;i++){
        if(sets.count(a[i])) continue;
        cout<<a[i]<<'\n';
    }
    return 0;
}