在一个包含多级目录与文件的文件系统中,每个文件有路径与内容。请设计算法删除内容完全相同的重复文件,仅保留每组中的一个,并返回被删除文件的完整路径列表。要求:
-
使用 DFS 与回溯遍历目录树;
-
说明如何比较文件内容以判定重复,确保正确性(例如文件大小预筛、分块读取、内容哈希);
-
处理异常情况(如循环链接、权限错误、超大文件)。
Follow-up:如何将该过程优化得更快?请讨论:
-
分层哈希/指纹(大小→块哈希→全量哈希)以减少 I/O;
-
并行化与限流策略;
-
去重索引的数据结构选择(哈希表、Trie/前缀树、布隆过滤器等);
-
时间与空间复杂度分析及工程权衡。