LeetCode 609. 在系统中查找重复文件

约 5 分钟
文章信息 6 个分类 3 个标签
分类
LeetCode CodeTop 中等 未解决 1-2 字节
标签
数组 字符串 哈希表

题目描述

✅ 609. 在系统中查找重复文件

image-20260929102011211

image-20260929102011351

题意分析

输入已经给出每个目录中的文件名和完整内容，不需要真的访问磁盘。把内容完全相同的文件分在一组，返回它们的完整路径，只保留至少有两个文件的组。

判重依据是内容，而不是文件名：不同目录、不同名字的文件也可能重复，同名文件的内容则可能不同。

解法：哈希表按内容分组

核心思路

[!blue]
哈希表的键保存内容字符串，值保存拥有该内容的完整路径列表。每处理一个文件，就把它的路径追加到对应内容组。相同内容必然落入同一组，不同内容仍由字符串相等性区分，无需枚举文件对。

按题目的单空格分隔格式，第一段是目录，后面每段是 文件名(内容)。找到文件段中的第一个左括号，之前是文件名，之后到最后一个右括号之前是内容；完整路径由目录、斜杠和文件名拼接，不包含括号或内容。

所有文件处理完后，内容相同的路径已经完整聚合。组大小大于一就表示重复，大小为一则丢弃。题目允许任意输出顺序，因此组内、组间都不需要额外排序。

解题步骤

  1. 逐条输入取出目录。
  2. 解析每个文件段的文件名和内容。
  3. 按内容分组，并加入完整路径。
  4. 筛掉只有一个文件的组。

代码实现

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        // 以内容为键：相同内容自动落入同一桶，无需两两比较。
        Map<String, List<String>> contentMap = new HashMap<>();

        for (String path : paths) {
            String[] parts = path.split(" ");
            String dir = parts[0];

            // 从 1 开始跳过目录段；只有目录时循环不进，边界自然成立。
            for (int i = 1; i < parts.length; i++) {
                // 文件名不含括号，第一个 '(' 即分界点。
                int idx = parts[i].indexOf('(');
                String fileName = parts[i].substring(0, idx);
                // 右端取 length - 1，正好剥掉结尾的 ')'。
                String content = parts[i].substring(idx + 1, parts[i].length() - 1);
                String fullPath = dir + "/" + fileName;

                contentMap.computeIfAbsent(content, key -> new ArrayList<>()).add(fullPath);
            }
        }

        List<List<String>> res = new ArrayList<>();

        for (List<String> group : contentMap.values()) {
            // 只有一个路径说明内容不重复，按题意不输出。
            if (group.size() > 1) {
                res.add(group);
            }
        }

        return res;
    }
}

import "strings"

func findDuplicate(paths []string) [][]string {
    // 以内容为键：相同内容自动落入同一桶，无需两两比较。
    contentMap := make(map[string][]string)

    for _, path := range paths {
        parts := strings.Split(path, " ")
        dir := parts[0]

        // 跳过目录段；只有目录时切片为空，循环不进。
        for _, file := range parts[1:] {
            // 文件名不含括号，第一个 '(' 即分界点。
            idx := strings.Index(file, "(")
            fileName := file[:idx]
            // 右端取 len(file)-1，正好剥掉结尾的 ')'。
            content := file[idx+1 : len(file)-1]

            fullPath := dir + "/" + fileName
            contentMap[content] = append(contentMap[content], fullPath)
        }
    }

    res := [][]string{}
    for _, group := range contentMap {
        // 只有一个路径说明内容不重复，按题意不输出。
        if len(group) > 1 {
            res = append(res, group)
        }
    }

    return res
}

复杂度分析

  • 时间复杂度：期望 $O(L+P)$，L 为输入总字符量，P 为生成全部完整路径的总字符量。
  • 空间复杂度：$O(L+P)$，保存内容键、完整路径及解析中间结果。

进阶：真实文件系统与大文件

  • 如何遍历目录：DFS 和 BFS 都能找到全部文件。使用目录迭代器逐项 DFS 时，只需保留当前目录链，栈深度随目录深度增长；BFS 要保存整层待访问目录，目录宽时队列可能很大。两者都不能省掉对每个文件的检查。
  • 内容达到 GB 级别：不要把完整内容作为内存中的键。先按文件大小分组，只有一个文件的大小组直接排除；同大小组可以先比较少量固定位置的数据，仍可能相同的文件再计算完整内容摘要。抽样相同只是候选，不能直接认定重复。
  • 每次只能读 1 KB：循环读取固定大小的块，增量更新摘要状态，直到文件末尾。只保留缓冲区和摘要，不必把所有块拼回内存；最后一块可以少于 1 KB。
  • 成本与优化：设文件数为 F、目录数为 D、实际读取的总字节数为 R，其中包含最后的内容复核。遍历和内容处理的期望时间为 $O(F+D+R)$，另计路径字符串处理成本；大文件场景主要耗时在磁盘读取。内存主要用于路径、文件大小、摘要和分组信息，内容只需固定大小的读缓冲。先按大小和抽样过滤，可以减少完整读取次数。
  • 如何避免误报：摘要相同不等于内容必然相同。对摘要相同的候选，再分块逐字节比较，按实际内容进一步分组，只有长度与每个字节都一致才认定重复。摘要碰撞只会增加比较工作，不会让不同内容进入同一结果组。

关键点总结

[!green]

  • 判重键是内容，不是名字或路径。
  • 完整路径需要目录、斜杠和文件名，不包含内容括号。
  • 重复目录前缀会在多条完整路径中重复出现，复杂度计入生成路径量。

易错点总结

[!yellow]

  • 按文件名分组：同名异内容文件被误判重复。
  • 把目录段当文件解析：它没有文件内容括号。
  • 输出单元素组：没有满足重复条件。
  • 完整路径漏掉分隔斜杠：返回格式错误。

相似题目

题目 难度 关联与区别
49. 字母异位词分组 中等 同样按规范键分组，本题键是文件内容，不能按文件名分组。
652. 寻找重复的子树 中等 相同子树需要结构和值的签名，相同文件只需内容键，都是用签名聚合同类对象。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/61841011
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！