哈希表题目:在系统中查找重复文件

news/2024/4/24 23:50:41/

文章目录

  • 题目
    • 标题和出处
    • 难度
    • 题目描述
      • 要求
      • 示例
      • 数据范围
      • 进阶
  • 解法
    • 思路和算法
    • 代码
    • 复杂度分析
  • 进阶问题答案
  • 后记

题目

标题和出处

标题:在系统中查找重复文件

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

难度

6 级

题目描述

要求

给定一个目录信息列表 paths \texttt{paths} paths,包括目录路径和该目录中的所有包含内容的文件,返回文件系统中的所有重复文件组的路径。你可以按任意顺序返回结果。

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

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

  • "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)" \texttt{"root/d1/d2/.../dm f1.txt(f1\_content) f2.txt(f2\_content) ... fn.txt(fn\_content)"} "root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

这意味着在目录 root/d1/d2/.../dm \texttt{root/d1/d2/.../dm} root/d1/d2/.../dm 下有 n \texttt{n} n 个文件 (f1.txt, f2.txt ... fn.txt) \texttt{(f1.txt, f2.txt ... fn.txt)} (f1.txt, f2.txt ... fn.txt),内容分别是 (f1_content, f2_content ... fn_content) \texttt{(f1\_content, f2\_content ... fn\_content)} (f1_content, f2_content ... fn_content)。注意: n ≥ 1 \texttt{n} \ge \texttt{1} n1 m ≥ 0 \texttt{m} \ge \texttt{0} m0。如果 m = 0 \texttt{m} = \texttt{0} m=0,则表示该目录是根目录。

输出是重复文件路径组的列表。对于每个组,它包含具有相同内容的文件的所有文件路径。文件路径是具有下列格式的字符串:

  • "directory_path/file_name.txt" \texttt{"directory\_path/file\_name.txt"} "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)"] \texttt{paths = ["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]} 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"]] \texttt{[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]} [["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)"] \texttt{paths = ["root/a 1.txt(abcd) 2.txt(efgh)","root/c 3.txt(abcd)","root/c/d 4.txt(efgh)"]} 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"]] \texttt{[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]} [["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]

数据范围

  • 1 ≤ paths.length ≤ 2 × 10 4 \texttt{1} \le \texttt{paths.length} \le \texttt{2} \times \texttt{10}^\texttt{4} 1paths.length2×104
  • 1 ≤ paths[i].length ≤ 3000 \texttt{1} \le \texttt{paths[i].length} \le \texttt{3000} 1paths[i].length3000
  • 1 ≤ sum(paths[i].length) ≤ 5 × 10 5 \texttt{1} \le \texttt{sum(paths[i].length)} \le \texttt{5} \times \texttt{10}^\texttt{5} 1sum(paths[i].length)5×105
  • paths[i] \texttt{paths[i]} paths[i] 由英语字母、数字、 ‘/’ \texttt{`/'} ‘/’ ‘.’ \texttt{`.'} ‘.’ ‘(’ \texttt{`('} ‘(’ ‘)’ \texttt{`)'} ‘)’ ‘ ’ \texttt{` '} ‘ ’ 组成
  • 你可以假设在同一目录中没有任何文件或目录共享相同的名称
  • 你可以假设每个给定的目录信息代表一个唯一的目录,目录路径和文件信息用一个空格分隔

进阶

  1. 假设给你一个真正的文件系统,你将如何搜索文件?深度优先搜索还是广度优先搜索?
  2. 如果文件内容非常大(GB 级别),你将如何修改你的解决方案?
  3. 如果每次只能读取 1 KB 的文件,你将如何修改你的解决方案?
  4. 修改后的解决方案的时间复杂度是多少?其中最消耗时间的部分和最消耗内存的部分是什么?如何优化?
  5. 如何确保你发现的重复文件不是误报?

解法

思路和算法

给定的数组 paths \textit{paths} paths 中的每个元素表示一个目录的路径以及该目录中的所有文件的文件名和文件内容。如果一个元素包含用空格分隔的 m m m 项,则可以将该元素使用空格作为分隔符创建长度为 m m m 的数组,数组中的第 0 0 0 项为目录路径,其余 m − 1 m - 1 m1 项分别为该目录中的每个文件的文件信息,包括文件名和文件内容,可以根据数组中的每个元素得到每个文件的绝对路径和文件内容。

为了找到重复文件,需要找到每种文件内容对应的文件列表,并判断文件列表中的文件个数,如果文件个数大于 1 1 1 则该文件列表为一组重复文件。可以使用哈希表记录每种文件内容对应的文件列表。

由于文件系统中的任意两个目录的路径都不同,任意两个文件的绝对路径都不同,因此不需要对目录的路径和文件的绝对路径做排重操作,使用列表表示每种文件内容的文件列表即可。

对于数组 paths \textit{paths} paths 中的每个元素,首先将该元素使用空格作为分隔符创建文件数组,然后对文件数组中的除了第 0 0 0 项以外的每一项得到文件的绝对路径和文件内容,在哈希表中将文件的绝对路径添加到文件内容的文件列表中。

遍历结束数组 paths \textit{paths} paths 之后,遍历哈希表,对于哈希表中的每种文件内容,如果对应的文件列表中的文件个数大于 1 1 1,则将该文件列表添加到结果中。

代码

class Solution {public List<List<String>> findDuplicate(String[] paths) {Map<String, List<String>> map = new HashMap<String, List<String>>();for (String path : paths) {String[] array = path.split(" ");StringBuffer directoryBuffer = new StringBuffer(array[0]);if (directoryBuffer.charAt(directoryBuffer.length() - 1) != '/') {directoryBuffer.append('/');}String directory = directoryBuffer.toString();int length = array.length;for (int i = 1; i < length; i++) {String fileNameContent = array[i];int fileNameContentLength = fileNameContent.length();int leftParenthesisIndex = -1;StringBuffer fileNameBuffer = new StringBuffer();for (int j = 0; j < fileNameContentLength && leftParenthesisIndex < 0; j++) {char c = fileNameContent.charAt(j);if (c == '(') {leftParenthesisIndex = j;} else {fileNameBuffer.append(c);}}String fileName = fileNameBuffer.toString();String content = fileNameContent.substring(leftParenthesisIndex + 1, fileNameContentLength - 1);String completeFileName = directory + fileName;map.putIfAbsent(content, new ArrayList<String>());map.get(content).add(completeFileName);}}List<List<String>> duplicates = new ArrayList<List<String>>();Set<Map.Entry<String, List<String>>> entries = map.entrySet();for (Map.Entry<String, List<String>> entry : entries) {String content = entry.getKey();List<String> files = entry.getValue();if (files.size() > 1) {duplicates.add(files);}}return duplicates;}
}

复杂度分析

  • 时间复杂度: O ( n ) O(n) O(n),其中 n n n 是文件系统中的文件总数。遍历文件系统中的全部文件并将每种文件内容和对应的文件列表存入哈希表,需要 O ( n ) O(n) O(n) 的时间,遍历哈希表得到结果也需要 O ( n ) O(n) O(n) 的时间。这里将字符串操作的时间视为 O ( 1 ) O(1) O(1)

  • 空间复杂度: O ( n ) O(n) O(n),其中 n n n 是文件系统中的文件总数。空间复杂度主要取决于哈希表,哈希表中需要存储每种文件内容对应的文件列表,空间是 O ( n ) O(n) O(n)。这里将字符串占用的空间视为 O ( 1 ) O(1) O(1)

进阶问题答案

  1. 假设给你一个真正的文件系统,你将如何搜索文件?深度优先搜索还是广度优先搜索?

    深度优先搜索和广度优先搜索的时间复杂度相同,因此应该根据空间复杂度决定使用哪种搜索方法。
    如果文件系统树结构的深度是 d d d,平均分支数是 f f f(即树结构中的每个目录结点平均有 f f f 个子结点),则深度优先搜索的空间复杂度是 O ( d ) O(d) O(d),广度优先搜索的空间复杂度是 O ( f d ) O(f^d) O(fd)。大多数情况下, O ( d ) O(d) O(d) 优于 O ( f d ) O(f^d) O(fd),因此大多数情况下应该使用深度优先搜索。

  2. 如果文件内容非常大(GB 级别),你将如何修改你的解决方案?

    如果文件内容非常大,则不能一次性存储文件的完整内容,因此需要将文件内容分块存储,并存储元数据,元数据包括文件名、文件大小、各分块的偏移量、各分块的哈希值等。
    其中,一个分块的哈希值等于该分块的内容使用特定哈希函数计算得到的结果,每个文件的所有分块的哈希值计算都使用同一个哈希函数。
    如果两个文件的内容相同,则这两个文件的大小一定也相同。因此,比较两个文件的内容是否相同时,首先比较两个文件的大小是否相同,如果大小不同则内容一定不同,如果大小相同再依次比较每个分块的哈希值是否相同,只要有一个分块的哈希值不同,则两个文件的内容不同,只有当每个分块的哈希值都相同时,才能认为两个文件的内容可能相同。使用哈希值进行比较虽然可以降低内存空间(只需要将哈希值存入内存,不需要将文件内容直接存入内存),但是可能存在误报的情况,问题 5 将提供解决方案。

  3. 如果每次只能读取 1 KB 的文件,你将如何修改你的解决方案?

    每次只能读取 1 KB 的文件,则每个分块的大小最多为 1 KB,因此使用问题 2 的解决方案,将每个分块的大小设为 1 KB。

  4. 修改后的解决方案的时间复杂度是多少?其中最消耗时间的部分和最消耗内存的部分是什么?如何优化?

    如果文件系统中的文件个数是 n n n,每个文件的平均大小是 k k k,则时间复杂度是 O ( k n 2 ) O(kn^2) O(kn2)。对于每个文件需要 O ( k ) O(k) O(k) 的时间计算元数据,其中计算每个分块哈希值的时间复杂度最高,共需要 O ( k n ) O(kn) O(kn) 的时间计算元数据。每两个文件之间都需要比较,比较次数是 n ( n − 1 ) 2 \dfrac{n(n - 1)}{2} 2n(n1),每次比较首先比较文件大小,然后比较每个分块的哈希值,因此最坏情况下每次比较的时间复杂度是 O ( k ) O(k) O(k),总时间复杂度是 O ( k n 2 ) O(kn^2) O(kn2)
    最消耗时间和内存的部分是哈希值的计算和存储。
    由于文件个数 n n n 和比较次数 n ( n − 1 ) 2 \dfrac{n(n - 1)}{2} 2n(n1) 无法减少,因此可以优化的方面只有哈希值的计算。在条件允许的情况下,将每个分块的大小增加,即可减少分块个数。

  5. 如何确保你发现的重复文件不是误报?

    误报的情况为两个文件的内容不同但是两个文件中的每个分块的哈希值对应相同。为了避免误报,当两个文件中的每个分块的哈希值都对应相同时,需要比较两个文件的内容,只有当内容相同时才能认为是重复文件。

后记

这道题的进阶问题涉及到搜索,搜索是在树和图中常用的算法。由于文件系统是一个树的结构,因此搜索文件需要使用到搜索算法。常见的搜索算法有深度优先搜索和广度优先搜索。

深度优先搜索的做法是从起点出发,沿着一条路搜索到底,然后依次回退到之前遍历的每一个位置,寻找其他尚未遍历的路并继续搜索,直到搜索完所有的位置。

广度优先搜索的做法是从起点出发,按照距离从近到远的顺序依次搜索每个位置。

关于树的搜索,将在树结构部分具体讲解。关于其他场景下的搜索,将在搜索算法部分具体讲解。


http://www.ppmy.cn/news/46794.html

相关文章

入门神经网络——浅层神经网络

文章目录 一、基础知识1.浅层神经网络介绍2.浅层神经网络的正向传播3.反向传播 二、浅层神经网络代码实例 一、基础知识 1.浅层神经网络介绍 此次构件浅层神经网络&#xff0c;相比于单神经元&#xff0c;浅层神经网络拥有多个神经元&#xff0c;因此又可以称为多神经元网络&…

Ubuntu 自带截图工具快捷键盘

PrtSc – 获取整个屏幕的截图并保存到 Pictures 目录。 Shift PrtSc – 获取屏幕的某个区域截图并保存到 Pictures 目录。 Alt PrtSc –获取当前窗口的截图并保存到 Pictures 目录。 Ctrl PrtSc – 获取整个屏幕的截图并存放到剪贴板。 Shift Ctrl PrtSc – 获取屏幕的某个…

【消费战略】解读100个食品品牌丨王小卤 4年10亿爆品破局

爆品破局 王小卤的聚焦发展! 王小卤创建于 2016 年&#xff0c;与饮料行业的独角兽元气森林同年。 相较于元气森林的快速增长&#xff0c;王小卤历经 三年坎坷之路&#xff0c;直至 2019 年才踏上高增长的赛道&#xff0c;实现四年十亿的增长。 “所有的消费品都值得重新 做…

SSM框架MyBatis 三种分页查询 PageHlper的使用以及五个参数的简单解释

SSM框架MyBatis 三种简单的分页查询 1. 基础分页查询&#xff08;环境在第一天的配置中有&#xff09; mapper也就是dao //查询总数Select("select count(*) from book;")int selectCount();//分页查询Select("select * from book limit #{currpage},#{size}&q…

KD2684S电机匝间耐电压测试仪

一、产品简介 试验仪适用于电机、变压器、电器线圈等这些由漆包线绕制的产品。因漆包线的绝缘涂敷层本身存在着质量问题&#xff0c;以及在绕线、嵌线、刮线、接头端部整形、绝缘浸漆、装配等工序工艺中不慎而引起绝缘层的损伤等&#xff0c;都会造成线圈层间或匝间绝缘层的绝缘…

NIFI从MySql中离线读取数据再导入到MySql中_03_来吧用NIFI实现_数据分页获取功能---大数据之Nifi工作笔记0038

之前使用querydatabasetable处理器来获取mysql中的数据,我们只能写死一个sql的查询语句,但是 实际引用环境中,我们的一张mysql的表,可能有上千万的数据,那么,不可能,我们把sql查询语句写死,这样一次性如果获取所有数据,那么压力太大了,我们怎么弄呢?找了很久没有找到相关教程…

Java 8 中使用 Lambda 表达式和 Stream API 解决 LeetCode 的两数之和问题

Java 8 中使用 Lambda 表达式和 Stream API 解决 LeetCode 的两数之和问题 当我们在面对一个数列&#xff0c;需要查找其中两个元素的和为给定目标值时&#xff0c;可以使用两数之和&#xff08;Two Sum&#xff09;问题来解决。这个问题在 LeetCode 上有很高的重要性和普遍性&…

机器人提示词工程师 Robotics Prompt Engineer

还没毕业&#xff0c;在校学习的各项技能都已经没用了&#xff0c;也别急着焦虑和忧伤&#xff0c;工业时代到信息时代&#xff0c;信息时代到智能时代&#xff0c;换代对每个普通人都是非常具有挑战性的&#xff0c;也是新一轮洗牌的开始。 机器人提示词工程师的核心竞争力包括…

3.3 二维随机变量条件分布

学习目标&#xff1a; 要学习二维随机变量的条件分布&#xff0c;我可能会采取以下步骤&#xff1a; 复习边缘分布和联合分布&#xff1a;首先需要了解二维随机变量的边缘分布和联合分布的概念以及相应的公式。 复习条件概率&#xff1a;学习条件概率的定义和计算公式&#x…

nodegui搭建/你好/打包

0、github连接问题 警告&#xff1a;如果你的网络有任何有任何有任何有任何有任何有任何有任何有任何有任何有任何连接 github 的问题&#xff0c;彻底放弃该框架 请转到其他框架 electron-egg教程、electron-egg官网&#xff0c;或其他electron项目 Tauri教程、Tauri官网 NW.…

【python零碎】

1. 拼接字符中&#xff0c;插入变量 >>> shepherd "Mary" >>> age 32 >>> stuff_in_string "Shepherd {} is {} years old.".format(shepherd, age) >>> print(stuff_in_string) Shepherd Mary is 32 years old. &…

2.3 连续性随机变量

思维导图&#xff1a; 学习目标&#xff1a; 我会按照以下步骤学习连续型随机变量&#xff1a; 复习概率论的基础知识&#xff0c;包括概率、期望、方差等概念和公式&#xff0c;以及离散型随机变量的概率分布函数和概率质量函数的概念和性质。 学习连续型随机变量的概念和性…

【Android安全】Soot 静态分析教程

参考教程 https://github.com/noidsirius/SootTutorial Windows Soot 环境配置 下载代码 git 拷贝仓库 git init git clone https://github.com/noidsirius/SootTutorial.git ./gradlew.bat build 报错&#xff1a;Unsupported class file major version 57 ./gradlew.b…

编译预处理:#if

用法 #if <expression> … #elif … #end <expression> 是整数常量比较的表达式&#xff0c;例如&#xff1a; defined表达式&#xff0c;例如 defined AAA, 或者 defined(AAA), 如果AAA是一个宏定义&#xff0c;return true&#xff0c;否则&#xff0c;return…

2023年全国最新安全员精选真题及答案55

百分百题库提供安全员考试试题、建筑安全员考试预测题、建筑安全员ABC考试真题、安全员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 81.&#xff08;单选题&#xff09;扣件式钢管模板支架的剪刀撑应用旋转扣件进行固定&…

HTML—javaEE

文章目录 1.认识HTML2.HTML标签的使用2.1注释2.2标题2.3段落2.4换行2.5字体加粗、斜体字、删除线、下划线2.6图片2.7超链接2.8表格2.9列表2.10表单标签2.11div2.12span 3.HTML特殊符号 1.认识HTML &#xff08;1&#xff09;HTML是网页的编程语言&#xff0c;文件的内容主要由…

lamp 架构的搭建

php 解释动态页面 php来连接数据库 mysql 页面信息和端口信息 存放数据 apache 前端web服务器&#xff0c;展现页面 源码编译安装这三个服务 配置下载apache: systemctl stop firewalld 关闭安全机制&#xff0c;防火墙 可以一条命令:systemctl is-enabled firewalld 和 s…

计组2.3——浮点数的表示和运算

计组2.3 浮点数 #mermaid-svg-hwjyO2bt7hFXy1eD {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-hwjyO2bt7hFXy1eD .error-icon{fill:#552222;}#mermaid-svg-hwjyO2bt7hFXy1eD .error-text{fill:#552222;stroke:#552…

Python Web 深度学习实用指南:第三部分

原文&#xff1a;Hands-On Python Deep Learning for the Web 协议&#xff1a;CC BY-NC-SA 4.0 译者&#xff1a;飞龙 本文来自【ApacheCN 深度学习 译文集】&#xff0c;采用译后编辑&#xff08;MTPE&#xff09;流程来尽可能提升效率。 不要担心自己的形象&#xff0c;只关…

MySQL客观题

MySQL客观题 在数据库的三级模式结构中&#xff0c;描述数据库中全体数据的全局逻辑结构和特性的是&#xff08; A &#xff09; A 模式 B 内模式 C 存储模式 D 外模式 数据库系统的特点是&#xff08; A &#xff09;、数据独立、减少数据冗余、避免数据不一致和加强了数据保…