列表

详情

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

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

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

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

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

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

 

示例 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"]]

 

提示：

 

进阶：

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<vector<string>> findDuplicate(vector<string>& paths) { } };

golang 解法, 执行用时: 40 ms, 内存消耗: 8.2 MB, 提交时间: 2023-05-10 10:30:37 

import "strings"

func findDuplicate(paths []string) [][]string {
    contentMap := make(map[string][]string)
    ans := make([][]string, 0)
    for _, pathString := range paths {
        // 路径分割
        paths := strings.Split(pathString, " ")
        document := ""
        for idx, path := range paths {
            if idx == 0 {
                document = path
            } else {
                // 按括号切分
                contents := strings.Split(path, "(")
                filePath := contents[0]
                content := contents[1][:len(contents[1]) - 1]

                fullPath := document + "/" + filePath
                contentMap[content] = append(contentMap[content], fullPath)
            }
        }
    }

    for _, contents := range contentMap {
        if len(contents) >= 2 {
            ans = append(ans, contents)
        }
    }

    return ans
}

golang 解法, 执行用时: 28 ms, 内存消耗: 8.3 MB, 提交时间: 2023-05-10 10:30:14 

func findDuplicate(paths []string) [][]string {
    txtMap := make(map[string][]string)
    for _, v := range paths{
        file := strings.Split(v, " ")
        for i:=1; i < len(file); i++{
            if len(file[i]) > 1{
                content := strings.Split(file[i], "(")
                txt := string(content[1][:len(content[1])-1])
                 if txtMap[txt] == nil{
                    txtMap[txt] = make([]string, 0)
                }
                txtMap[txt] = append(txtMap[txt], file[0] +"/"+ content[0] )
            }
        }
    }
    res := make([][]string, 0)
    for _, v := range txtMap{
        if len(v) > 1{
            res = append(res, v)
        }
        
    }
    return res
}

cpp 解法, 执行用时: 96 ms, 内存消耗: 33.2 MB, 提交时间: 2023-05-10 10:29:41 

class Solution {
public:
  vector<vector<string>> findDuplicate(vector<string> &paths) {
    //key为文件内容，value为目录+文件名
    unordered_map<string, vector<string>> m;
    for (string &s : paths) {
      //' '前的字符串即为目录，为其追加一个'/'
      int start = s.find(' ');
      string path = s.substr(0, start).append(1, '/');
      //寻找`(`
      int leftBracket = s.find('(', start);
      while (leftBracket != -1) {
        //根据'('和' '的位置确定文件名
        string fileName = s.substr(start + 1, leftBracket - start - 1);
        //寻找`)`
        int rightBracket = s.find(')', leftBracket);
        //根据'('和')'的位置确定文件内容，将其作为key，目录和文件名作为value
        m[s.substr(leftBracket + 1, rightBracket - leftBracket - 1)].emplace_back(path + fileName);
        //继续寻找该目录的下一个文件
        start = rightBracket + 1;
        leftBracket = s.find('(', start);
      }
    }
    //找出具有重复内容的文件路径
    vector<vector<string>> result;
    for (auto &p : m) {
      if (p.second.size() >= 2) {
        result.emplace_back(p.second);
      }
    }
    return result;
  }
};

python3 解法, 执行用时: 72 ms, 内存消耗: 23.2 MB, 提交时间: 2023-05-10 10:29:20 

class Solution:
    def findDuplicate(self, paths: List[str]) -> List[List[str]]:
        hashtag = {}  #定义一个字典
        for p in paths:  #对目录进行遍历
            s = []
            s = p.split(' ')  #将字符串s按空格分开，其中s[0]表示目录，
            #print(s)
            for val in s[1:]:  #对文件进行遍历
                t, key = val.split("(")  #将文件名和内容分开，这里直接用"("分开即可
                if key not in hashtag:
                    hashtag[key] = [s[0] + '/' + t]
                else:
                    hashtag[key].append(s[0] + '/' + t)  #将内容相同的文件及其对应的目录储存
        res = []
        for key in hashtag:
            if len(hashtag[key]) >= 2:  #判断是否为重复文件
                res.append(hashtag[key])
        return res

java 解法, 执行用时: 25 ms, 内存消耗: 52.2 MB, 提交时间: 2023-05-10 10:28:56 

public class Solution {
    public List < List < String >> findDuplicate(String[] paths) {
        HashMap < String, List < String >> map = new HashMap < > ();
        for (String path: paths) {
            String[] values = path.split(" ");
            for (int i = 1; i < values.length; i++) {
                String[] name_cont = values[i].split("\\(");
                name_cont[1] = name_cont[1].replace(")", "");
                List < String > list = map.getOrDefault(name_cont[1], new ArrayList < String > ());
                list.add(values[0] + "/" + name_cont[0]);
                map.put(name_cont[1], list);
            }
        }
        List < List < String >> res = new ArrayList < > ();
        for (String key: map.keySet()) {
            if (map.get(key).size() > 1)
                res.add(map.get(key));
        }
        return res;
    }
}

上一题

© 2025 leetcode.cn