在系统中查找重复文件

标签: 数组 哈希表 字符串

难度: Medium

给你一个目录信息列表 paths ，包括目录路径，以及该目录中的所有文件及其内容，请你按路径返回文件系统中的所有重复文件。答案可按 任意顺序 返回。

一组重复的文件至少包括 两个 具有完全相同内容的文件。

输入 列表中的单个目录信息字符串的格式如下：

  • "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着，在目录 root/d1/d2/.../dm 下，有 n 个文件 ( f1.txt, f2.txt ... fn.txt ) 的内容分别是 ( f1_content, f2_content ... fn_content ) 。注意：n >= 1 且 m >= 0 。如果 m = 0 ，则表示该目录是根目录。

输出 是由 重复文件路径组 构成的列表。其中每个组由所有具有相同内容文件的文件路径组成。文件路径是具有下列格式的字符串：

  • "directory_path/file_name.txt"

示例 1：

输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)","root 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

示例 2：

输入：paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]
输出：[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

提示：

  • 1 <= paths.length <= 2 * 104
  • 1 <= paths[i].length <= 3000
  • 1 <= sum(paths[i].length) <= 5 * 105
  • paths[i] 由英文字母、数字、字符 '/'、'.'、'('、')' 和 ' ' 组成
  • 你可以假设在同一目录中没有任何文件或目录共享相同的名称。
  • 你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。

进阶：

  • 假设您有一个真正的文件系统，您将如何搜索文件？广度搜索还是宽度搜索？
  • 如果文件内容非常大（GB级别），您将如何修改您的解决方案？
  • 如果每次只能读取 1 kb 的文件，您将如何修改解决方案？
  • 修改后的解决方案的时间复杂度是多少？其中最耗时的部分和消耗内存的部分是什么？如何优化？
  • 如何确保您发现的重复文件不是误报？

Submission

运行时间: 43 ms

内存: 22.8 MB

class Solution:      
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        dict_file_content = {}
        res = []
        for path in paths:
            temp = path.split(" ")
            path_root = temp[0]
            for i in range(1, len(temp)):
                file = temp[i].split("(")
                file_path = path_root + '/' + file[0]
                file_content = file[1][:-1]

                if file_content in dict_file_content:
                    dict_file_content[file_content].append(file_path)
                else:
                    dict_file_content[file_content] = [file_path]
        
        for key, value in dict_file_content.items():
            if len(value) > 1:
                res.append(value)

        return res

Explain

该题解的思路如下： 1. 遍历 paths 列表中的每一个目录信息字符串 2. 将目录信息按空格拆分成根目录路径和文件信息 3. 遍历文件信息，将每个文件拆分成文件路径和文件内容 4. 使用一个哈希表 dict_file_content 存储文件内容和对应的文件路径列表的映射关系 - 如果文件内容已存在于哈希表中，将当前文件路径追加到对应的路径列表 - 如果文件内容不存在于哈希表中，创建一个新的路径列表并存储到哈希表 5. 遍历哈希表，将路径列表长度大于1的所有路径列表加入结果 res 中 6. 返回结果 res，即所有重复文件的路径列表

时间复杂度: O(n * m)

空间复杂度: O(n * m)

class Solution:      
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        # 创建哈希表用于存储文件内容和对应的文件路径列表
        dict_file_content = {}
        # 创建结果列表
        res = []
        # 遍历目录信息列表
        for path in paths:
            # 按空格拆分目录信息为根目录路径和文件信息
            temp = path.split(" ")
            path_root = temp[0]
            # 遍历文件信息
            for i in range(1, len(temp)):
                # 将文件信息拆分为文件名和文件内容
                file = temp[i].split("(")
                file_path = path_root + '/' + file[0]
                file_content = file[1][:-1]

                # 判断文件内容是否已存在于哈希表中
                if file_content in dict_file_content:
                    # 如果存在，将当前文件路径追加到对应的路径列表
                    dict_file_content[file_content].append(file_path)
                else:
                    # 如果不存在，创建一个新的路径列表并存储到哈希表
                    dict_file_content[file_content] = [file_path]
        
        # 遍历哈希表
        for key, value in dict_file_content.items():
            # 如果路径列表长度大于1，说明存在重复文件
            if len(value) > 1:
                # 将重复文件的路径列表加入结果中
                res.append(value)

        # 返回所有重复文件的路径列表
        return res

Explore

哈希表（也称为字典或映射）非常适合这个问题，因为它提供了快速的查找、插入和删除操作。在这个题解中，需要频繁地检查某个文件内容是否已存在于映射中，并根据这个检查结果迅速更新文件路径列表。使用哈希表可以在平均情况下达到常数时间复杂度的查找性能，这使得处理大量数据时更为高效。此外，哈希表通过键（本题中为文件内容）到值（文件路径列表）的映射，自然地支持这种类型的数据关联，使得数据的组织和访问都变得直接和简单。

在题解代码中，文件信息是以括号 '(' 分隔文件名和文件内容的。为了正确提取文件内容，代码首先使用 '(' 将字符串分割成文件名和文件内容两部分。然后，通过字符串切片 file[1][:-1] 移除文件内容字符串的最后一个字符，即闭合的括号 ')'。这种方式假设文件内容中的最后一个括号是闭合括号，并且没有考虑文件内容内部可能包含括号的情况。若文件内容中确实包含多个括号，则需要进一步的处理，例如查找最后一个 ')' 来正确切分字符串。当前的简单实现可能不足以处理所有复杂情况，但在题目给定的格式约定下是有效的。

哈希表中的冲突指的是两个不同的键通过哈希函数得到了相同的哈希值。在Python中，字典（内部使用哈希表实现）处理哈希冲突的常见策略是使用开放寻址或链表法。在开放寻址法中，如果一个索引已被占用，哈希表会尝试找到下一个空闲的索引。在链表法中，每个槽位存储一个指向键值对链表的指针，冲突发生时，新的键值对会被添加到链表的末尾。由于这些细节通常是由Python语言的实现（如CPython）封装的，用户不需要自己处理冲突，可以直接利用字典的高效和便捷性质。