LeetCode 1487. 保证文件名唯一

2022-03-10 HGNULB 约 6 分钟

文章信息 6 个分类 3 个标签

分类

题目描述

✅ 1487. 保证文件名唯一

题意分析

按顺序创建 names 里的每个文件夹。如果名字没被占用，直接用；如果已被占用，系统会自动加后缀 (k)，k 取使得 name(k) 尚未被占用的最小正整数。返回每次实际创建出来的名字数组。

三个细节决定成败。第一，「最小的 k」是从 1 开始试的，不是从「这个名字出现过几次」开始。第二，带后缀生成出来的名字本身也会占用命名空间——["pes","pes(1)"] 里第二个 pes(1) 是用户直接给的，它必须占住 pes(1)，导致后面再来一个 pes 时只能拿 pes(2)。第三，输入里本来就可能出现带括号的名字，它们不是我们生成的，但同样参与占用，不需要也不应该去解析括号里的数字。

约束里 names.length 到 $5 \times 10^4$，名字长度到 20。这个规模明确排除了「每次都从 k = 1 重头试」的朴素写法——最坏情况下 $5 \times 10^4$ 个相同的名字会让总试探次数达到 $O(n^2)$，即 $1.25 \times 10^9$ 次字符串拼接与哈希查询，必然超时。能不能把重复试探压掉，是这道题从「简单模拟」升级为「中等」的唯一原因，也是面试官想看的东西。

边界：全部名字互不相同（无需任何后缀）；全部名字相同（依次得到 a、a(1)、a(2) …）；用户提前占用了将来会被生成的名字（如 ["gta","gta(1)","gta"]，第三个只能是 gta(2)）；甚至提前占用了更靠后的号（如 ["a","a(3)","a","a","a"]，依次得到 a(1)、a(2)、a(4)——a(3) 被跳过）。

解法：哈希表记录下一个可用后缀

核心思路

只用“已占用集合”时，每次重名都从后缀 1 开始试，会在大量同名输入上重复扫描。用一张哈希表同时保存占用状态和下一次探测起点，可以把重复工作摊平。

定义 nextSuffix[name]：名字 name 已被占用，且下次发生冲突时从该正整数后缀开始尝试。键集合就是全部已占用名字；新名字首次出现时记为 1。

遇到冲突时，从记录值 k 开始检查 name(k)。用户可能提前创建过某个带后缀名字，所以仍需循环跳过已占用候选。找到后要同时更新 nextSuffix[name] = k + 1，并登记生成名 nextSuffix[candidate] = 1。

不变量是：处理完任意输入前缀后，表中的键恰好等于已经输出的名字，且每个基础名的探测指针不会回退。正确性说明：未占用分支直接使用原名，显然取到最小选择；冲突分支从所有已证明不可用的较小后缀之后开始，并逐个检查到首个空位，因此得到最小合法 k。每个输出随即登记，所以结果始终唯一。

解题步骤

创建哈希表 nextSuffix 和等长结果数组。

名字未占用时原样输出，并将其探测起点设为 1。

名字已占用时，从表中记录的 k 开始生成候选，循环跳过已有名字。

找到空位后推进基础名的 k，并登记新生成名字。

按输入顺序返回结果。

["gta","gta(1)","gta","avalon"] 会输出 ["gta","gta(1)","gta(2)","avalon"]。["a","a(3)","a","a","a"] 中最后三个 a 依次得到 a(1)、a(2)、a(4)，验证了候选仍需循环探测。

代码实现

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String[] getFolderNames(String[] names) {
        Map<String, Integer> nextSuffix = new HashMap<>();
        String[] answer = new String[names.length];

        for (int i = 0; i < names.length; i++) {
            String name = names[i];
            if (!nextSuffix.containsKey(name)) {
                answer[i] = name;
                nextSuffix.put(name, 1);
                continue;
            }

            int suffix = nextSuffix.get(name);
            String candidate = name + "(" + suffix + ")";
            while (nextSuffix.containsKey(candidate)) {
                suffix++;
                candidate = name + "(" + suffix + ")";
            }

            answer[i] = candidate;
            nextSuffix.put(name, suffix + 1);
            nextSuffix.put(candidate, 1);
        }
        return answer;
    }
}

import "strconv"

func getFolderNames(names []string) []string {
	nextSuffix := make(map[string]int)
	answer := make([]string, len(names))

	for i, name := range names {
		suffix, exists := nextSuffix[name]
		if !exists {
			answer[i] = name
			nextSuffix[name] = 1
			continue
		}

		candidate := name + "(" + strconv.Itoa(suffix) + ")"
		for {
			if _, occupied := nextSuffix[candidate]; !occupied {
				break
			}
			suffix++
			candidate = name + "(" + strconv.Itoa(suffix) + ")"
		}

		answer[i] = candidate
		nextSuffix[name] = suffix + 1
		nextSuffix[candidate] = 1
	}
	return answer
}

复杂度分析

时间复杂度：均摊 $O(nL)$。每个基础名的后缀指针只前进，所有探测总次数为线性级；L 为生成名字的最大长度。

空间复杂度：$O(nL)$。哈希表保存所有已占用名字；结果数组属于输出。

关键点总结

一张表同时承担“是否占用”和“从哪里继续试”两个职责。

记录值只是探测下界，用户可能提前占用后缀，因此 while 不能省。

生成名也必须登记，因为它同样占用命名空间。

输入中的括号只是普通字符，不要解析或改写其含义。

易错点总结

每次从后缀 1 重试：大量相同名字会退化为平方级探测。

把一次冲突检查写成 if：["a","a(1)","a"] 会再次生成已占用的 a(1)；必须循环到 a(2)。

忘记登记生成名：后续出现同名字面量时会重复输出。

新名字的初始后缀设为 0：["a","a"] 会生成非法的 a(0)。

解析输入中的括号："a(1)" 本身就是完整基础名，重复时应生成 "a(1)(1)"。

更新基础名为 k 而不是 k + 1：结果仍可能正确，但下次会重复检查刚占用的候选。

相似题目

题目	难度	考察点
1166. 设计文件系统	中等	同为命名空间管理，但要校验父路径存在，键是层级路径而非扁平名字
535. TinyURL 的加密与解密	中等	也要保证生成的标识不冲突，但用自增 ID 或随机串，考察双向映射的维护
609. 在系统中查找重复文件	中等	按文件内容而非文件名分组，重点在字符串解析与多值哈希表
217. 存在重复元素	简单	只问是否有重复，哈希集合的最裸用法，没有「冲突后如何改名」的后续逻辑
1512. 好数对的数目	简单	同为边扫边查历史表，但表里存的是计数并用于累加贡献而非判定占用
187. 重复的DNA序列	中等	用哈希表统计定长子串出现次数，考察如何避免重复输出同一个子串