题目描述

给你一个长度为n的字符串数组names。你将会在文件系统中创建n个文件夹：在第i分钟，新建名为names[i]的文件夹。

由于两个文件不能共享相同的文件名，因此如果新建文件夹使用的文件名已经被占用，系统会以(k)的形式为新文件夹的文件名添加后缀，其中k是能保证文件名唯一的最小正整数。

返回长度为n的字符串数组，其中ans[i]是创建第i个文件夹时系统分配给该文件夹的实际名称。

思路与算法

我们考虑使用一个map记录<当前文件名， 最小可用下标>，并用一个vector存储最终答案。先判断当前文件名是否出现过，如果未出现，则初始化<文件名， 1> 放入map中，同时，将对应文件名放入vector中；若当前文件名出现过，则从map中映射的最小可用下标开始向后枚举，得到第一个未被使用过的最小下标i，得到目标文件名str，存入答案数组中，并将map中对应文件名的最小可用下标更新至i+1，同时，将<str, 1>的映射关系存入map中。

代码

class Solution {
public:
    vector<string> getFolderNames(vector<string>& names) {
        int n = names.size();
        unordered_map<string, int>  M;
        vector<string> res;
        for(int i = 0; i < n; i++){
            string tmp = "";
            if(M.find(names[i]) == M.end()){
                M[names[i]] = 1;
                tmp = names[i];  
            }else{
                int k = M[names[i]];
                tmp =  names[i] + '(' + to_string(k) + ')';
                while(M.find(tmp) != M.end()){
                    k++;
                    tmp =  names[i] + '(' + to_string(k) + ')';
                }    
                M[names[i]] = k+1;
                M[tmp] = 1;
            }
            res.push_back(tmp);
        }
        return res;
    }
};

复杂度分析

• 时间复杂度：只经过一遍数组元素的遍历，因此时间复杂度O(n)。
• 空间复杂度： 创建了辅助空间map和res，因此空间复杂度O(n)。

心得

起初对每个文件名的下标查找采用依次从1开始向后遍历，当一个文件名出现次数较多时，会有较多无用的搜索，从而导致了超时。因此，改进后采用记录当前可用的最小下标i，为了防止加上当前最小下标后的文件名在之前输入时已经出现过的情况，这里需要从此下标i开始向后寻找第一个没有使用过的下标。这样，可以避免每次都会重复访问i之前的下标，从而降低时间复杂度。