难度: Medium
Submission
运行时间: 192 ms
内存: 23.5 MB
class FileSharing:
def __init__(self, m: int):
self.cur = 0
self.chunks = m
self.reused = []
self.user_chunks = defaultdict(set)
def join(self, ownedChunks: List[int]) -> int:
if self.reused:
userID = heappop(self.reused)
else:
self.cur += 1
userID = self.cur
self.user_chunks[userID] = set(ownedChunks)
return userID
def leave(self, userID: int) -> None:
heappush(self.reused, userID)
self.user_chunks.pop(userID)
def request(self, userID: int, chunkID: int) -> List[int]:
if chunkID < 1 or chunkID > self.chunks:
return []
res = []
for k, v in self.user_chunks.items():
if chunkID in v:
res.append(k)
if res:
self.user_chunks[userID].add(chunkID)
return sorted(res)
# Your FileSharing object will be instantiated and called as such:
# obj = FileSharing(m)
# param_1 = obj.join(ownedChunks)
# obj.leave(userID)
# param_3 = obj.request(userID,chunkID)
Explain
这个题解使用哈希表 user_chunks 来记录每个用户拥有的文件块编号。当用户加入时，如果有之前离开的用户，则复用其 ID，否则分配一个新的 ID。当用户离开时，将其 ID 加入重用 ID 的小顶堆 reused 中。当用户请求一个文件块时，遍历所有用户，找到拥有该文件块的用户 ID，返回其有序列表，并将该文件块编号加入请求用户的拥有列表中。
时间复杂度: O(n + k log k)
空间复杂度: O(n * m)
class FileSharing:
def __init__(self, m: int):
self.cur = 0 # 当前用户 ID
self.chunks = m # 文件块总数
self.reused = [] # 重用的用户 ID 小顶堆
self.user_chunks = defaultdict(set) # 用户拥有的文件块编号哈希表
def join(self, ownedChunks: List[int]) -> int:
if self.reused:
userID = heappop(self.reused) # 复用离开的用户 ID
else:
self.cur += 1
userID = self.cur # 分配新的用户 ID
self.user_chunks[userID] = set(ownedChunks) # 记录用户拥有的文件块编号
return userID
def leave(self, userID: int) -> None:
heappush(self.reused, userID) # 将离开的用户 ID 加入重用小顶堆
self.user_chunks.pop(userID) # 删除用户拥有的文件块记录
def request(self, userID: int, chunkID: int) -> List[int]:
if chunkID < 1 or chunkID > self.chunks: # 文件块编号无效
return []
res = []
for k, v in self.user_chunks.items(): # 遍历所有用户
if chunkID in v: # 找到拥有该文件块的用户
res.append(k)
if res:
self.user_chunks[userID].add(chunkID) # 将该文件块加入请求用户的拥有列表
return sorted(res) # 返回拥有该文件块的用户 ID 有序列表
# Your FileSharing object will be instantiated and called as such:
# obj = FileSharing(m)
# param_1 = obj.join(ownedChunks)
# obj.leave(userID)
# param_3 = obj.request(userID,chunkID)
Explore
在`join`方法中，如果存在多个可重用的用户 ID，选择的 ID 是基于最小值标准，即小顶堆的顶部元素，这是因为小顶堆能够保证每次都能快速获取最小的元素。使用小顶堆的主要原因是其能够高效地支持常数时间的最小元素查找，以及对堆的插入和删除操作的对数时间复杂度，这使得用户 ID 的管理更为高效和有序。
在`leave`方法中，立即删除用户的文件块记录可能会影响到同时进行的`request`操作，特别是在多线程或并发环境中。如果`request`操作正在访问被删除的用户数据，则可能导致数据访问错误或不一致。为避免这种情况，可以实施锁机制或使用事务内存等并发控制技术来同步对`user_chunks`字典的访问，确保在修改数据时不会被其他操作干扰。
当前的设计中，即使用户已经拥有所请求的文件块，`request`方法仍会将该文件块添加到用户的拥有列表中，这可能导致重复记录。为优化这一点，可以在添加文件块之前检查用户是否已经拥有该文件块。如果已经拥有，则无需再次添加，这样可以避免不必要的重复记录，提高系统的效率和准确性。
在实例化FileSharing类时，参数`m`指定了文件块的总数。这个参数的主要作用是在`request`方法中进行边界检查，确保用户请求的文件块编号在有效范围内（即1到m之间）。通过在`request`方法开始处检查文件块编号是否有效，从而确保不会请求不存在的文件块，这是防止请求超出总数文件块的机制。