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

Categories:

题目描述
思路分析
1. 解法一：哈希表（推荐）
相似题目

题目描述

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

思路分析

解法一：哈希表（推荐）

核心思路：

遍历每条路径字符串，按空格拆分得到目录路径和若干 文件名(内容) 片段

解析每个文件片段，提取文件内容作为 key，将完整文件路径（目录/文件名）存入哈希表

最终过滤哈希表中值列表长度 >= 2 的条目，即为重复文件组

复杂度分析：

时间复杂度：O(n * k)，其中 n 表示路径字符串数量，k 表示每条路径字符串的平均长度

空间复杂度：O(n * k)，哈希表存储所有文件路径

class Solution {
    public List<List<String>> findDuplicate(String[] paths) {
        // key: 文件内容，value: 包含该内容的完整文件路径列表
        Map<String, List<String>> map = new HashMap<>();

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

            for (int i = 1; i < parts.length; i++) {
                // 拆分文件名和内容
                int idx = parts[i].indexOf('(');
                String fileName = parts[i].substring(0, idx);
                String content = parts[i].substring(idx + 1, parts[i].length() - 1);

                String fullPath = dir + "/" + fileName;
                map.computeIfAbsent(content, k -> new ArrayList<>()).add(fullPath);
            }
        }

        // 过滤出重复文件组
        List<List<String>> result = new ArrayList<>();
        for (List<String> group : map.values()) {
            if (group.size() >= 2) {
                result.add(group);
            }
        }

        return result;
    }
}

func findDuplicate(paths []string) [][]string {
    // key: 文件内容，value: 包含该内容的完整文件路径列表
    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]
            content := file[idx+1 : len(file)-1]

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

    // 过滤出重复文件组
    result := [][]string{}
    for _, group := range contentMap {
        if len(group) >= 2 {
            result = append(result, group)
        }
    }

    return result
}

相似题目

题目	难度	考察点
1. 两数之和	简单	哈希表
49. 字母异位词分组	中等	哈希表、字符串
128. 最长连续序列	中等	哈希表
202. 快乐数	简单	哈希表
290. 单词规律	简单	哈希表、字符串
349. 两个数组的交集	简单	哈希表

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2021/61841011