[LeetCode] 609. Find Duplicate File in System

sf190404 发布于2019-08-19 11:11 / 2699人阅读

Problem

Given a list of directory info including directory path, and all the files with contents in this directory, you need to find out all the groups of duplicate files in the file system in terms of their paths.

A group of duplicate files consists of at least two files that have exactly the same content.

A single directory info string in the input list has the following format:

"root/d1/d2/.../dm f1.txt(f1_content) f2.txt(f2_content) ... fn.txt(fn_content)"

It means there are n files (f1.txt, f2.txt ... fn.txt with content f1_content, f2_content ... fn_content, respectively) in directory root/d1/d2/.../dm. Note that n >= 1 and m >= 0. If m = 0, it means the directory is just the root directory.

The output is a list of group of duplicate file paths. For each group, it contains all the file paths of the files that have the same content. A file path is a string that has the following format:

"directory_path/file_name.txt"

Example 1:
Input:

["root/a 1.txt(abcd) 2.txt(efgh)", "root/c 3.txt(abcd)", "root/c/d 4.txt(efgh)", "root 4.txt(efgh)"]

Output:

[["root/a/2.txt","root/c/d/4.txt","root/4.txt"],["root/a/1.txt","root/c/3.txt"]]

Note:
No order is required for the final output.
You may assume the directory name, file name and file content only has letters and digits, and the length of file content is in the range of [1,50].
The number of files given is in the range of [1,20000].
You may assume no files or directories share the same name in the same directory.
You may assume each given directory info represents a unique directory. Directory path and file info are separated by a single blank space.

Follow-up beyond contest:

Imagine you are given a real file system, how will you search files? DFS or BFS?
If the file content is very large (GB level), how will you modify your solution?
If you can only read the file by 1kb each time, how will you modify your solution?
What is the time complexity of your modified solution? What is the most time-consuming part and memory consuming part of it? How to optimize?
How to make sure the duplicated files you find are not false positive?

Solution

class Solution {
    public List> findDuplicate(String[] paths) {
        List> res = new ArrayList<>();
        if (paths == null || paths.length == 0) return res;
        Map> map = new HashMap<>();
        
        for (String str: paths) {
            String[] parts = str.split(" ");
            String rootPath = parts[0];
            
            for (int i = 1; i < parts.length; i++) {
                String child = parts[i];
                for (int j = 0; j < child.length(); j++) {
                    //assuming there"s multiple "(", find the first
                    if (child.charAt(j) == "(") {
                        String childPath = child.substring(0, j);
                        String finalPath = rootPath + "/" + childPath;
                        String content = child.substring(j+1, child.length()-1);
                        if (!map.containsKey(content)) {
                            map.put(content, new ArrayList());
                        }
                        map.get(content).add(finalPath);
                    }
                    
                }
            }
            
        }
        
        for (Map.Entry> entry: map.entrySet()) {
            if (entry.getValue().size() > 1) res.add(entry.getValue());
        }
        return res;
    }
}

GPU云服务器云服务器 FIND_IN_SET DUPLICATE 隆昌路609ucloud LeetCode

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/77161.html

LeetCode[287] Find the Duplicate Number

摘要：复杂度思路每次通过二分法找到一个值之后，搜索整个数组，观察小于等于这个数的个数。考虑，小于这个位置的数的个数应该是小于等于这个位置的。要做的就是像找中的环一样，考虑重复的点在哪里。考虑用快慢指针。代码把一个指针放回到开头的地方 LeetCode[287] Find the Duplicate Number Given an array nums containing n + 1 in...

canopus4u 2019-08-14 15:03 评论0 收藏0
[LeetCode] Find the Duplicate Number

Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...

MoAir 2019-08-15 15:53 评论0 收藏0
[LeetCode] 287. Find the Duplicate Number

Problem Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate nu...

rickchen 2019-08-16 14:25 评论0 收藏0
[Leetcode] Find the Duplicate Number 找到重复数字

摘要：暴力法复杂度时间空间思路如果不用空间的话，最直接的方法就是选择一个数，然后再遍历整个数组看是否有跟这个数相同的数就行了。二分法复杂度时间空间思路实际上，我们可以根据抽屉原理简化刚才的暴力法。 Find the Duplicate Number Given an array nums containing n + 1 integers where each integer is bet...

chnmagnus 2019-08-14 12:39 评论0 收藏0
[Leetcode] Contains Duplicate 包含重复

摘要：代码集合法复杂度时间空间思路同样使用集合，但这次我们要维护集合的大小不超过，相当于是记录一个宽度为的窗口中出现过的数字。 Contains Duplicate I Given an array of integers, find if the array contains any duplicates. Your function should return true if any v...

rozbo 2019-08-14 12:28 评论0 收藏0