一、题目描述
给你一个目录信息列表 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 * 10^41 <= paths[i].length <= 30001 <= sum(paths[i].length) <= 5 * 10^5paths[i]由英文字母、数字、字符'/'、'.'、'('、')'和' '组成- 你可以假设在同一目录中没有任何文件或目录共享相同的名称。
- 你可以假设每个给定的目录信息代表一个唯一的目录。目录路径和文件信息用单个空格分隔。
二、解题思路
- 使用一个HashMap来存储文件内容与文件路径的映射关系。键是文件内容，值是一个包含相同内容文件路径的列表。
- 遍历输入的paths数组，对每个字符串进行处理，以获取目录路径和文件信息。
- 对于每个文件，提取出文件名和文件内容，然后将文件路径（目录路径+文件名）添加到HashMap中对应内容的列表中。
- 遍历HashMap，找出所有值（文件路径列表）的长度大于1的键值对，即这些键对应的文件内容是重复的。
- 将这些重复的文件路径列表添加到结果列表中。
三、具体代码
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;public class Solution {public List<List<String>> findDuplicate(String[] paths) {// 创建一个HashMap来存储文件内容与文件路径的映射关系Map<String, List<String>> contentMap = new HashMap<>();// 遍历每个目录信息for (String path : paths) {// 分割目录路径和文件信息String[] parts = path.split(" ");String dir = parts[0];// 遍历文件信息for (int i = 1; i < parts.length; i++) {// 找到文件名和文件内容的开始和结束位置int start = parts[i].indexOf('(');int end = parts[i].indexOf(')');// 提取文件内容String content = parts[i].substring(start + 1, end);// 构建完整的文件路径String filePath = dir + "/" + parts[i].substring(0, start);// 将文件路径添加到HashMap中contentMap.computeIfAbsent(content, k -> new ArrayList<>()).add(filePath);}}// 创建结果列表List<List<String>> result = new ArrayList<>();// 遍历HashMap，找出所有重复的文件内容for (List<String> filePaths : contentMap.values()) {if (filePaths.size() > 1) {result.add(filePaths);}}return result;}
}
四、时间复杂度和空间复杂度
1. 时间复杂度
-
遍历HashMap中的所有值，这个操作的时间复杂度是O(k)，其中k是HashMap中所有列表的总长度。
综上所述，总的时间复杂度是O(n * m + k)。由于k是所有文件的总数，而每个文件都会被遍历一次，所以k <= n * m。因此，时间复杂度可以简化为O(n * m)。
2. 空间复杂度
- HashMap的空间复杂度是O(k)，其中k是不同文件内容的数量。在最坏的情况下，所有文件内容都是唯一的，所以k接近于所有文件的总数。
- 结果列表
result的空间复杂度是O(k)，因为每个唯一的文件内容都可能在结果列表中有一个对应的列表。
综上所述，总的空间复杂度是O(k)，其中k是不同文件内容的数量。在最坏的情况下，空间复杂度接近于O(n * m)，因为每个文件都可能有一个唯一的文件内容。然而，在实际情况中，文件内容的数量通常会远小于文件的总数，因此空间复杂度通常会小于O(n * m)。
五、总结知识点
-
数据结构：
HashMap：用于存储键值对，其中键是文件内容，值是包含相同内容文件路径的列表。ArrayList：用于存储文件路径列表，以及最终的结果列表。
-
字符串操作：
-
循环和条件语句：
for循环：用于遍历数组或集合中的元素。if语句：用于条件判断。
-
Map操作：
computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)：如果指定的键尚未与值相关联（或映射到null），则尝试使用给定的映射函数计算其值，并将其输入到此映射中，除非null。
-
函数式编程：
- 使用Lambda表达式作为
computeIfAbsent方法的参数，这是一种简化的匿名函数写法。
- 使用Lambda表达式作为
-
Java语法：
- 变量声明和初始化。
- 方法定义和返回值。
- 类型推断，例如在Lambda表达式中不需要显式指定参数类型。
-
面向对象编程：
- 类定义：
public class Solution。 - 方法定义：
public List<List<String>> findDuplicate(String[] paths)。
- 类定义：
-
集合框架：
- 使用
List和Map接口及其实现类ArrayList和HashMap。
- 使用
以上就是解决这个问题的详细步骤，希望能够为各位提供启发和帮助。
