題目

標(biāo)題和出處

標(biāo)題：在系統(tǒng)中查找重復(fù)文件

出處：609. 在系統(tǒng)中查找重復(fù)文件

難度

6 級

題目描述

要求

給定一個(gè)目錄信息列表 $\text{paths}$，包括目錄路徑和該目錄中的所有包含內(nèi)容的文件，返回文件系統(tǒng)中的所有重復(fù)文件組的路徑。你可以按任意順序返回結(jié)果。

一組重復(fù)的文件至少包括兩個(gè)具有完全相同內(nèi)容的文件。

輸入列表中的單個(gè)目錄信息字符串的格式如下：

• $\text{"root/d1/d2/.../dm?f1.txt(f1\_content)?f2.txt(f2\_content)?...?fn.txt(fn\_content)"}$

這意味著在目錄 $\text{root/d1/d2/.../dm}$ 下有 $\text{n}$ 個(gè)文件 $\text{(f1.txt,?f2.txt?...?fn.txt)}$，內(nèi)容分別是 $\text{(f1\_content,?f2\_content?...?fn\_content)}$。注意：$\text{n}\ge \text{1}$ 且 $\text{m}\ge \text{0}$。如果 $\text{m}=\text{0}$，則表示該目錄是根目錄。

輸出是重復(fù)文件路徑組的列表。對于每個(gè)組，它包含具有相同內(nèi)容的文件的所有文件路徑。文件路徑是具有下列格式的字符串：

• $\text{"directory\_path/file\_name.txt"}$

示例

示例 1：

輸入：$\text{paths?=?["root/a?1.txt(abcd)?2.txt(efgh)",?"root/c?3.txt(abcd)",?"root/c/d?4.txt(efgh)",?"root?4.txt(efgh)"]}$
輸出：$\text{[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]}$

示例 2：

輸入：$\text{paths?=?["root/a?1.txt(abcd)?2.txt(efgh)","root/c?3.txt(abcd)","root/c/d?4.txt(efgh)"]}$
輸出：$\text{[["root/a/2.txt","root/c/d/4.txt"],["root/a/1.txt","root/c/3.txt"]]}$

數(shù)據(jù)范圍

• $\text{1}\le \text{paths.length}\le \text{2}\times {\text{10}}^{\text{4}}$
• $\text{1}\le \text{paths[i].length}\le \text{3000}$
• $\text{1}\le \text{sum(paths[i].length)}\le \text{5}\times {\text{10}}^{\text{5}}$
• $\text{paths[i]}$ 由英語字母、數(shù)字、$\text{‘/’}$、$\text{‘.’}$、$\text{‘(’}$、$\text{‘)’}$ 和 $\text{‘?’}$ 組成
• 你可以假設(shè)在同一目錄中沒有任何文件或目錄共享相同的名稱
• 你可以假設(shè)每個(gè)給定的目錄信息代表一個(gè)唯一的目錄，目錄路徑和文件信息用一個(gè)空格分隔

進(jìn)階

1. 假設(shè)給你一個(gè)真正的文件系統(tǒng)，你將如何搜索文件？深度優(yōu)先搜索還是廣度優(yōu)先搜索？
2. 如果文件內(nèi)容非常大（GB 級別），你將如何修改你的解決方案？
3. 如果每次只能讀取 1 KB 的文件，你將如何修改你的解決方案？
4. 修改后的解決方案的時(shí)間復(fù)雜度是多少？其中最消耗時(shí)間的部分和最消耗內(nèi)存的部分是什么？如何優(yōu)化？
5. 如何確保你發(fā)現(xiàn)的重復(fù)文件不是誤報(bào)？

解法

思路和算法

給定的數(shù)組 $\text{paths}$ 中的每個(gè)元素表示一個(gè)目錄的路徑以及該目錄中的所有文件的文件名和文件內(nèi)容。如果一個(gè)元素包含用空格分隔的 $m$ 項(xiàng)，則可以將該元素使用空格作為分隔符創(chuàng)建長度為 $m$ 的數(shù)組，數(shù)組中的第 $0$ 項(xiàng)為目錄路徑，其余 $m?1$ 項(xiàng)分別為該目錄中的每個(gè)文件的文件信息，包括文件名和文件內(nèi)容，可以根據(jù)數(shù)組中的每個(gè)元素得到每個(gè)文件的絕對路徑和文件內(nèi)容。

為了找到重復(fù)文件，需要找到每種文件內(nèi)容對應(yīng)的文件列表，并判斷文件列表中的文件個(gè)數(shù)，如果文件個(gè)數(shù)大于 $1$ 則該文件列表為一組重復(fù)文件?？梢允褂霉１碛涗浢糠N文件內(nèi)容對應(yīng)的文件列表。

由于文件系統(tǒng)中的任意兩個(gè)目錄的路徑都不同，任意兩個(gè)文件的絕對路徑都不同，因此不需要對目錄的路徑和文件的絕對路徑做排重操作，使用列表表示每種文件內(nèi)容的文件列表即可。

對于數(shù)組 $\text{paths}$ 中的每個(gè)元素，首先將該元素使用空格作為分隔符創(chuàng)建文件數(shù)組，然后對文件數(shù)組中的除了第 $0$ 項(xiàng)以外的每一項(xiàng)得到文件的絕對路徑和文件內(nèi)容，在哈希表中將文件的絕對路徑添加到文件內(nèi)容的文件列表中。

遍歷結(jié)束數(shù)組 $\text{paths}$ 之后，遍歷哈希表，對于哈希表中的每種文件內(nèi)容，如果對應(yīng)的文件列表中的文件個(gè)數(shù)大于 $1$，則將該文件列表添加到結(jié)果中。

代碼

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;}
}

復(fù)雜度分析

• 時(shí)間復(fù)雜度：$O(n)$，其中 $n$ 是文件系統(tǒng)中的文件總數(shù)。遍歷文件系統(tǒng)中的全部文件并將每種文件內(nèi)容和對應(yīng)的文件列表存入哈希表，需要 $O(n)$ 的時(shí)間，遍歷哈希表得到結(jié)果也需要 $O(n)$ 的時(shí)間。這里將字符串操作的時(shí)間視為 $O(1)$。

• 空間復(fù)雜度：$O(n)$，其中 $n$ 是文件系統(tǒng)中的文件總數(shù)?？臻g復(fù)雜度主要取決于哈希表，哈希表中需要存儲每種文件內(nèi)容對應(yīng)的文件列表，空間是 $O(n)$。這里將字符串占用的空間視為 $O(1)$。

進(jìn)階問題答案

1. 假設(shè)給你一個(gè)真正的文件系統(tǒng)，你將如何搜索文件？深度優(yōu)先搜索還是廣度優(yōu)先搜索？

   深度優(yōu)先搜索和廣度優(yōu)先搜索的時(shí)間復(fù)雜度相同，因此應(yīng)該根據(jù)空間復(fù)雜度決定使用哪種搜索方法。
   如果文件系統(tǒng)樹結(jié)構(gòu)的深度是 $d$，平均分支數(shù)是 $f$（即樹結(jié)構(gòu)中的每個(gè)目錄結(jié)點(diǎn)平均有 $f$ 個(gè)子結(jié)點(diǎn)），則深度優(yōu)先搜索的空間復(fù)雜度是 $O(d)$，廣度優(yōu)先搜索的空間復(fù)雜度是 $O(f^d)$。大多數(shù)情況下，$O(d)$ 優(yōu)于 $O(f^d)$，因此大多數(shù)情況下應(yīng)該使用深度優(yōu)先搜索。

2. 如果文件內(nèi)容非常大（GB 級別），你將如何修改你的解決方案？

   如果文件內(nèi)容非常大，則不能一次性存儲文件的完整內(nèi)容，因此需要將文件內(nèi)容分塊存儲，并存儲元數(shù)據(jù)，元數(shù)據(jù)包括文件名、文件大小、各分塊的偏移量、各分塊的哈希值等。
   其中，一個(gè)分塊的哈希值等于該分塊的內(nèi)容使用特定哈希函數(shù)計(jì)算得到的結(jié)果，每個(gè)文件的所有分塊的哈希值計(jì)算都使用同一個(gè)哈希函數(shù)。
   如果兩個(gè)文件的內(nèi)容相同，則這兩個(gè)文件的大小一定也相同。因此，比較兩個(gè)文件的內(nèi)容是否相同時(shí)，首先比較兩個(gè)文件的大小是否相同，如果大小不同則內(nèi)容一定不同，如果大小相同再依次比較每個(gè)分塊的哈希值是否相同，只要有一個(gè)分塊的哈希值不同，則兩個(gè)文件的內(nèi)容不同，只有當(dāng)每個(gè)分塊的哈希值都相同時(shí)，才能認(rèn)為兩個(gè)文件的內(nèi)容可能相同。使用哈希值進(jìn)行比較雖然可以降低內(nèi)存空間（只需要將哈希值存入內(nèi)存，不需要將文件內(nèi)容直接存入內(nèi)存），但是可能存在誤報(bào)的情況，問題 5 將提供解決方案。

3. 如果每次只能讀取 1 KB 的文件，你將如何修改你的解決方案？

   每次只能讀取 1 KB 的文件，則每個(gè)分塊的大小最多為 1 KB，因此使用問題 2 的解決方案，將每個(gè)分塊的大小設(shè)為 1 KB。

4. 修改后的解決方案的時(shí)間復(fù)雜度是多少？其中最消耗時(shí)間的部分和最消耗內(nèi)存的部分是什么？如何優(yōu)化？

   如果文件系統(tǒng)中的文件個(gè)數(shù)是 $n$，每個(gè)文件的平均大小是 $k$，則時(shí)間復(fù)雜度是 $O(k{n}^2)$。對于每個(gè)文件需要 $O(k)$ 的時(shí)間計(jì)算元數(shù)據(jù)，其中計(jì)算每個(gè)分塊哈希值的時(shí)間復(fù)雜度最高，共需要 $O(kn)$ 的時(shí)間計(jì)算元數(shù)據(jù)。每兩個(gè)文件之間都需要比較，比較次數(shù)是 $\frac{n(n?1)}{2}$，每次比較首先比較文件大小，然后比較每個(gè)分塊的哈希值，因此最壞情況下每次比較的時(shí)間復(fù)雜度是 $O(k)$，總時(shí)間復(fù)雜度是 $O(k{n}^2)$。
   最消耗時(shí)間和內(nèi)存的部分是哈希值的計(jì)算和存儲。
   由于文件個(gè)數(shù) $n$ 和比較次數(shù) $\frac{n(n?1)}{2}$ 無法減少，因此可以優(yōu)化的方面只有哈希值的計(jì)算。在條件允許的情況下，將每個(gè)分塊的大小增加，即可減少分塊個(gè)數(shù)。

5. 如何確保你發(fā)現(xiàn)的重復(fù)文件不是誤報(bào)？

   誤報(bào)的情況為兩個(gè)文件的內(nèi)容不同但是兩個(gè)文件中的每個(gè)分塊的哈希值對應(yīng)相同。為了避免誤報(bào)，當(dāng)兩個(gè)文件中的每個(gè)分塊的哈希值都對應(yīng)相同時(shí)，需要比較兩個(gè)文件的內(nèi)容，只有當(dāng)內(nèi)容相同時(shí)才能認(rèn)為是重復(fù)文件。

后記

這道題的進(jìn)階問題涉及到搜索，搜索是在樹和圖中常用的算法。由于文件系統(tǒng)是一個(gè)樹的結(jié)構(gòu)，因此搜索文件需要使用到搜索算法。常見的搜索算法有深度優(yōu)先搜索和廣度優(yōu)先搜索。

深度優(yōu)先搜索的做法是從起點(diǎn)出發(fā)，沿著一條路搜索到底，然后依次回退到之前遍歷的每一個(gè)位置，尋找其他尚未遍歷的路并繼續(xù)搜索，直到搜索完所有的位置。

廣度優(yōu)先搜索的做法是從起點(diǎn)出發(fā)，按照距離從近到遠(yuǎn)的順序依次搜索每個(gè)位置。

關(guān)于樹的搜索，將在樹結(jié)構(gòu)部分具體講解。關(guān)于其他場景下的搜索，將在搜索算法部分具體講解。