LEETCODE 1500. Design a File Sharing System 解题思路分析

题目大意：

设计一个文件共享系统

我们使用一个文件共享系统来分享一个由m个区块构成的超大文件，区块的id从1到m。

当一个用户加入到这个系统后，系统会分配给他一个唯一的id，这个id在系统中只能有一名用户使用。不过当该用户退出系统后，这个id则可以被其他用户复用。

每个用户都可以指定请求文件的区块，系统会返回给用户一个清单，其中包含当前系统中拥有该区块的用户列表。如果至少有一位用户拥有该区块，那么当前用户也能获得该区块。

请实现 FileSharing 类:

• FileSharing(int m) 构造函数，构造一个拥有m个区块的FileSharing对象.
• int join(int[] ownedChunks): 一名用户加入系统，他拥有文件的某些区块。系统将分配给该他一个用户id，须保证这个id是最小并且没有被其他用户所占用。函数返回值为该用户分配到的id
• void leave(int userID): id为 userID 的用户退出系统后，你不能再通过该用户获得任何文件区块。
• int[] request(int userID, int chunkID): id为userID 的用户请求id为chunkID的区块。请返回拥有该区块的用户id列表，并使用用户id对列表进行升序排列。

Follow-ups:

• What happens if the system identifies the user by their IP address instead of their unique ID and users disconnect and connect from the system with the same IP?
• If the users in the system join and leave the system frequently without requesting any chunks, will your solution still be efficient?
• If all each user join the system one time, request all files and then leave, will your solution still be efficient?
• If the system will be used to share n files where the ith file consists of m[i], what are the changes you have to do?

Example:

Input:
["FileSharing","join","join","join","request","request","leave","request","leave","join"]
[[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]]
Output:
[null,1,2,3,[2],[1,2],null,[],null,1]
Explanation:
FileSharing fileSharing = new FileSharing(4); // We use the system to share a file of 4 chunks.
fileSharing.join([1, 2]);    // A user who has chunks [1,2] joined the system, assign id = 1 to them and return 1.
fileSharing.join([2, 3]);    // A user who has chunks [2,3] joined the system, assign id = 2 to them and return 2.
fileSharing.join([4]);       // A user who has chunk [4] joined the system, assign id = 3 to them and return 3.
fileSharing.request(1, 3);   // The user with id = 1 requested the third file chunk, as only the user with id = 2 has the file, return [2] . Notice that user 1 now has chunks [1,2,3].
fileSharing.request(2, 2);   // The user with id = 2 requested the second file chunk, users with ids [1,2] have this chunk, thus we return [1,2]. We don't care if the user has the file and request it, we just return all the users that can give them the file.
fileSharing.leave(1);        // The user with id = 1 left the system, all the file chunks with them are no longer available for other users.
fileSharing.request(2, 1);   // The user with id = 2 requested the first file chunk, no one in the system has this chunk, we return empty list [].
fileSharing.leave(2);        // The user with id = 2 left the system, all the file chunks with them are no longer available for other users.
fileSharing.join([]);        // A user who doesn't have any chunks joined the system, assign id = 1 to them and return 1. Notice that ids 1 and 2 are free and we can reuse them.

Constraints:

• 1 <= m <= 10^5
• 0 <= ownedChunks.length <= min(100, m)
• 1 <= ownedChunks[i] <= m
• Values of ownedChunks are unique.
• 1 <= chunkID <= m
• userID is guaranteed to be a user in the system if you assign the IDs correctly. 
• At most 10^4 calls will be made to join, leave and request.
• Each call to leave will have a matching call for join.

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1500

解题思路分析：

这是leetcode的第1500道题。记得我刚入刷题这个坑时，总共才有不到800题，一转眼，题目数量都快翻倍了。

言归正传，这是一道设计题，题目主要目的是让我们设计一个合理高效的数据存储方式。本题实际上有两个复杂点：

1. 保证新用户的id一定是未使用id中最小的。
2. 如何统计当前拥有每个区块的用户列表，并对他们进行排序。

对于第一个问题，难点主要出现在用户退出系统后，该用户曾使用过的id会重新对其他人开放，如果没有这个条件，题目就会变得简单许多，只要将用户id一直向上累加即可。不过这个问题也不复杂，我们定义一个自增的id用来作为新用户默认的id。另外再使用一个集合来存储用户退出系统后恢复为可用状态的id列表list。当一名用户进入系统后，如果list中不存在元素，那么使用默认的自增id。如果list中存在元素，那么从list中取出一个最小的使用即可。这里我们可以使用PriorityQueue来存储该list，由于PriorityQueue自动带有排序属性，因此每次取出的id一定是queue中最小的那个。

第二个问题主要是在讨论如何存储当前系统中用户与他们各自拥有区块的关系。这个问题也不难，使用一个Map即可。map的key为用户id，value为他当前拥有的区块列表，该列表我们使用Set进行存储。使用Set的原因有2，其一是为了去重，其二我们通过Set类可以轻松的判断出它是否包含某个元素（contains），这个判断的时间复杂度为O(1)。（注意List的contains方法的时间复杂度是O(n)。）此外，由于题目要求对用户id进行排序，因此这里我们可以使用TreeMap，TreeMap与PriorityQueue类似，自带排序属性，默认情况下map中的key是升序排序的。

接下来具体看下每个方法的实现方式：

FileSharing(int m)：构造函数中不用做太多的工作，初始化一下上文提到的PriorityQueue和TreeMap即可。

int join(int[] ownedChunks)：先查看PriorityQueue中是否存在可以复用的id，如果queue中元素个数大于0，poll出一个最小的作为当前用户的id。反之如果queue中没有元素，那么我们将当前自增id作为当前用户id，同时自增id加一。取得用户id后，我们使用用户id作为key，该用户拥有的区块列表作为value，将其存入TreeMap。

void leave(int userID)：用户退出系统后，我们使用该用户id将TreeMap中对应的数据清空。同时将这个id添加进PriorityQueue中，等待被复用。

int[] request(int userID, int chunkID): 首先循环TreeMap中的每一个key（用户id），查看每一个用户的区块列表中是否包含目标区块id，如果包含，我们将当前用户id加入返回列表。循环结束后，由于key是自动排序过的，因此添加到列表中的元素也是被排序过的状态。另外如果列表不为空，说明当前用户可以得到该区块，我们需要将该区块添加到该用户的区块列表中。

实现代码：

Map<Integer,Set<Integer>> map; // 用户id，该用户拥有的区块列表
int uid=1; // 自增用户id
PriorityQueue<Integer> leavedIds; // 可复用的用户的id列表
public FileSharing(int m) {
    map=new TreeMap<>();
    leavedIds=new PriorityQueue<>();
}

public int join(List<Integer> ownedChunks) {
    int userID=uid; // 默认使用自增用户id
    // 如果复用列表不为空，优先使用服用列表中最小的
    if(leavedIds.size()>0) userID=leavedIds.poll();
    // 反之使用自增id，使用后id加一
    else uid++;
    // 将当前用户以及他拥有的区块列表存入map
    map.put(userID, new HashSet<>(ownedChunks));
    return userID;
}

public void leave(int userID) {
    map.remove(userID); // 从map中删除该用户信息
    leavedIds.offer(userID); // 将该用户id添加至可复用id的queue列表中
}

public List<Integer> request(int userID, int chunkID) {
    List<Integer> res = new ArrayList<>(); // 返回结果
    for(int user : map.keySet()){ // 循环map中的key（用户id）
        // 如果当前用户拥有该区块，将该用户添加至返回结果
        if(map.get(user).contains(chunkID)) res.add(user);
    }
    // 如果返回结果中元素个数大于0，
    // 说明userID这个用户可以得到chunkID这个区块
    if(res.size()>0){
        // 将userID这个用户的区块列表中添加chunkID这个区块
        Set<Integer> set=map.get(userID);
        set.add(chunkID);
        map.put(userID,set);
    }
    return res;
}

本题解法执行时间为125ms。

Runtime: 125 ms, faster than 100.00% of Java online submissions for Design a File Sharing System.

Memory Usage: 51.1 MB, less than 100.00% of Java online submissions for Design a File Sharing System.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1500-design-a-file-sharing-system-解题思路分析/