摘要: 最小可用 ID 的维护
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
本文看一个设计题,数据结构的设计比较复杂,同时还需要处理最小可用 ID 的维护。
$1 题目
我们需要使用一套文件分享系统来分享一个非常大的文件,该文件由 m 个从 1 到 m 编号的文件块组成。
当用户加入系统时,系统应为其注册一个独有的 ID。这个独有的 ID 应当被相应的用户使用一次,但是当用户离开系统时,其 ID 应可以被(后续新注册的用户)再次使用。
用户可以请求文件中的某个指定的文件块,系统应当返回拥有这个文件块的所有用户的 ID。如果用户收到 ID 的非空列表,就表示成功接收到请求的文件块。
实现 FileSharing 类:
FileSharing(int m) 初始化该对象,文件有 m 个文件块。
int join(int[] ownedChunks):一个新用户加入系统,并拥有文件的一些文件块。系统应当为该用户注册一个 ID,该 ID 应是未被其他用户占用的最小正整数。返回注册的 ID。
void leave(int userID):ID 为 userID 的用户将离开系统,你不能再从该用户提取文件块了。
int[] request(int userID, int chunkID):ID 为 userID 的用户请求编号为 chunkID 的文件块。返回拥有这个文件块的所有用户的 ID 所构成的列表或数组,按升序排列。
提示:
1 | 1 <= m <= 10^5 |
示例:
输入:
[“FileSharing”,”join”,”join”,”join”,”request”,”request”,”leave”,”request”,”leave”,”join”]
[[4],[[1,2]],[[2,3]],[[4]],[1,3],[2,2],[1],[2,1],[2],[[]]]
输出:
[null,1,2,3,[2],[1,2],null,[],null,1]
解释:
FileSharing fileSharing = new FileSharing(4); // 我们用该系统分享由 4 个文件块组成的文件。fileSharing.join([1, 2]); // 一个拥有文件块 [1,2] 的用户加入系统,为其注册 id = 1 并返回 1。
fileSharing.join([2, 3]); // 一个拥有文件块 [2,3] 的用户加入系统,为其注册 id = 2 并返回 2。
fileSharing.join([4]); // 一个拥有文件块 [4] 的用户加入系统,为其注册 id = 3 并返回 3。
fileSharing.request(1, 3); // id = 1 的用户请求第 3 个文件块,只有 id = 2 的用户拥有文件块,返回 [2] 。注意,现在用户 1 现拥有文件块 [1,2,3]。
fileSharing.request(2, 2); // id = 2 的用户请求第 2 个文件块,id 为 [1,2] 的用户拥有该文件块,所以我们返回 [1,2] 。
fileSharing.leave(1); // id = 1 的用户离开系统,其所拥有的所有文件块不再对其他用户可用。
fileSharing.request(2, 1); // id = 2 的用户请求第 1 个文件块,系统中没有用户拥有该文件块,所以我们返回空列表 [] 。
fileSharing.leave(2); // id = 2 的用户离开系统。
fileSharing.join([]); // 一个不拥有任何文件块的用户加入系统,为其注册 id = 1 并返回 1 。注意,id 1 和 2 空闲,可以重新使用。
- 当系统以用户的 IP 地址而不是独有 ID 来识别用户,且用户断开连接后以相同 IP 重新连接系统时,会发生什么?
- 当用户频繁加入并退出系统,且该用户不请求任何文件块时,你的解决方案仍然保持高效吗?
- 当所有用户同时加入系统,请求所有文件并离开时,你的解决方案仍然保持高效吗?
- 如果系统用于分享 n 个文件,其中第 i 个文件由 m[i] 组成,你需要如何修改?
$2 题解
算法:设计
数据结构设计
1 | vector<set<int>> chunks_info; // chunks_info[chunkID] := 持有 chunkID 的 userID 升序 |
最小可用 ID 的维护
用一个变量维护当前系统中维护的最大 id,可能是当前在线的 id,也可能是维护在堆中的以下线 id。
用一个最小堆维护释放时刻不是当时的最大 id 的那些 id。
- 获取 id 时,如果堆中有,则从堆中取,这是以前分配过但是现在空闲的 id,否则取
++max_id
。 - 释放 id 时,如果释放的是当前最大 id,则将
max_id
自减,否则压堆。
代码 (C++)
1 | class FileSharing { |