新建文件夹(1)｜字符串哈希

第三题 - NewFolder(1)

题目跳转：新建文件夹(1)。

也是一道水题，用 STL 的 unordered_map/ map 存一下某一个字符串出现的次数就可以了。由于 $N$ 比较大，因此如果直接用双层循环遍历的话绝对会超时。

但需要注意的是，map 的单次插入/查询的时间复杂度约为 $O(\log_2 N)$。因此本题的综合时间复杂度约为 $O(N \log_2 N)$。

本题的 AC 代码如下：

#include <iostream>
#include <algorithm>
#include <unordered_map>
using namespace std;

int n;
string str[200005];
unordered_map<string, int> map;

int main(){
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> str[i];
        map[str[i]] += 1;
        int cnt = map[str[i]];
        if (cnt == 1)
            cout << str[i] << endl;
        else 
            cout << str[i] << "(" << cnt-1 << ")" << endl;
    }
    return 0;
}