leetcode
leetcode 351 ~ 400
电话目录管理系统

电话目录管理系统

难度:

标签:

题目描述

代码结果

运行时间: 60 ms, 内存: 20.3 MB


/*
 * 题目:电话目录管理系统
 * 编号:379
 * 
 * 题目思路:
 * 1. 创建一个 PhoneDirectory 类来管理电话号码。
 * 2. 使用一个 Set<Integer> 来跟踪可用的电话号码和一个 Set<Integer> 来跟踪已使用的电话号码。
 * 3. 提供三个主要方法:get() 获取一个未使用的号码、check() 检查号码是否可用、release() 释放一个号码。
 */
 
import java.util.HashSet;
import java.util.Set;
import java.util.stream.IntStream;
 
public class PhoneDirectory {
    private Set<Integer> available;
    private Set<Integer> used;
 
    public PhoneDirectory(int maxNumbers) {
        available = IntStream.range(0, maxNumbers).collect(HashSet::new, Set::add, Set::addAll);
        used = new HashSet<>();
    }
 
    public int get() {
        if (available.isEmpty()) {
            return -1; // 若无可用号码,返回 -1
        }
        int number = available.iterator().next();
        available.remove(number);
        used.add(number);
        return number;
    }
 
    public boolean check(int number) {
        return available.contains(number);
    }
 
    public void release(int number) {
        if (used.contains(number)) {
            used.remove(number);
            available.add(number);
        }
    }
}

解释

方法:

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

时间复杂度:

O(1)

空间复杂度:

O(n) 其中 n 是电话目录能容纳的电话号码总数

代码细节讲解

🦆
在`PhoneDirectory`的实现中,为什么选择使用集合(set)来管理电话号码而不是其他数据结构如列表或队列?
在`PhoneDirectory`的设计中,选择使用集合(set)主要基于其在某些操作上具有高效的时间复杂度。特别是,集合的`add`和`remove`操作通常可以在平均O(1)时间内完成,这使得电话号码的分配和释放非常高效。此外,检查一个号码是否存在于集合中的操作也是O(1)时间复杂度,这对于`check`方法尤为重要。相比之下,如果使用列表,检查元素存在性和移除元素通常需要O(n)时间;而使用队列虽然可以快速移除,但检查元素存在性也是O(n)。因此,集合在这种需求下提供了更好的性能。
🦆
如何处理`get`方法在集合为空时连续调用的情况,以及这种情况下的性能影响是什么?
当`get`方法在集合为空时被调用,它将返回-1,表示没有可用的电话号码。如果连续调用这个方法而集合仍然为空,它将连续返回-1。这种情况下,性能影响主要是由于重复无效调用。每次调用`get`方法时,都需要检查集合是否为空,这是一个O(1)操作。因此,即使在集合为空的情况下频繁调用此方法,性能影响也是可控的,并且对系统资源的消耗较低。
🦆
在`release`方法中,如果尝试释放一个已经存在于集合中的号码,会发生什么?是否需要额外的逻辑来处理这种情况?
在`release`方法中,如果尝试释放的电话号码已经存在于集合中,实际上并不会发生任何变化,因为集合的性质是不允许重复的元素存在。这种情况下不需要额外的逻辑处理,因为添加一个已存在的元素到集合中是一个无操作(no-op)。`set.add`方法会检查元素是否存在,如果存在则不会进行任何操作。因此,即使在这种情况下调用`release`,也不会对集合的状态或性能产生负面影响。

相关问题