电话目录管理系统

难度: Medium

Submission

运行时间: 60 ms

内存: 20.3 MB

class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        self.avail = set(range(maxNumbers))

    def get(self) -> int:
        return self.avail.pop() if self.avail else -1

    def check(self, number: int) -> bool:
        return number in self.avail

    def release(self, number: int) -> None:
        if number not in self.avail:
            self.avail.add(number)


# Your PhoneDirectory object will be instantiated and called as such:
# obj = PhoneDirectory(maxNumbers)
# param_1 = obj.get()
# param_2 = obj.check(number)
# obj.release(number)

Explain

该题解使用两个集合来管理电话号码的分配和释放。`availableNumbers` 集合存储所有当前可用的电话号码，而 `usedNumbers` 集合存储所有已经被分配的电话号码。通过这种方式，我们可以快速检查、分配和释放电话号码。初始化时，所有电话号码都被视为可用。当请求一个电话号码时，从 `availableNumbers` 中移除一个号码并加入到 `usedNumbers` 中。检查电话号码是否可用时，只需查看它是否还在 `availableNumbers` 中。释放电话号码时，从 `usedNumbers` 中移除并重新加入到 `availableNumbers` 中，使其再次可用。

时间复杂度: O(1)

空间复杂度: O(n) 其中 n 是电话目录能容纳的电话号码总数

class PhoneDirectory:

    def __init__(self, maxNumbers: int):
        self.maxNumbers = maxNumbers  # 最大电话号码数量
        self.availableNumbers = set(range(maxNumbers))  # 初始化时，全部电话号码都是可用的
        self.usedNumbers = set()  # 初始时，没有电话号码被使用

    def get(self) -> int:
        if not self.availableNumbers:
            return -1  # 如果没有可用的号码，则返回 -1
        number = self.availableNumbers.pop()  # 从可用号码中获取一个号码
        self.usedNumbers.add(number)  # 将这个号码标记为已使用
        return number

    def check(self, number: int) -> bool:
        return number in self.availableNumbers  # 检查号码是否可用

    def release(self, number: int) -> None:
        if number in self.usedNumbers:
            self.usedNumbers.remove(number)  # 从已使用集合中移除
            self.availableNumbers.add(number)  # 重新加入到可用号码集合中

Explore

在`PhoneDirectory`的设计中，选择使用集合（set）主要基于其在某些操作上具有高效的时间复杂度。特别是，集合的`add`和`remove`操作通常可以在平均O(1)时间内完成，这使得电话号码的分配和释放非常高效。此外，检查一个号码是否存在于集合中的操作也是O(1)时间复杂度，这对于`check`方法尤为重要。相比之下，如果使用列表，检查元素存在性和移除元素通常需要O(n)时间；而使用队列虽然可以快速移除，但检查元素存在性也是O(n)。因此，集合在这种需求下提供了更好的性能。

当`get`方法在集合为空时被调用，它将返回-1，表示没有可用的电话号码。如果连续调用这个方法而集合仍然为空，它将连续返回-1。这种情况下，性能影响主要是由于重复无效调用。每次调用`get`方法时，都需要检查集合是否为空，这是一个O(1)操作。因此，即使在集合为空的情况下频繁调用此方法，性能影响也是可控的，并且对系统资源的消耗较低。

在`release`方法中，如果尝试释放的电话号码已经存在于集合中，实际上并不会发生任何变化，因为集合的性质是不允许重复的元素存在。这种情况下不需要额外的逻辑处理，因为添加一个已存在的元素到集合中是一个无操作（no-op）。`set.add`方法会检查元素是否存在，如果存在则不会进行任何操作。因此，即使在这种情况下调用`release`，也不会对集合的状态或性能产生负面影响。