LeetCode 第379题：电话目录管理系统

📖 文章摘要

本文详细解析LeetCode第379题“电话目录管理系统”，这是一道设计题。文章提供了基于哈希集合和队列的解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升数据结构设计能力的读者。

核心知识点： 设计、哈希集合、队列 难度等级： 中等 推荐人群： 具有基础算法知识，想要提升数据结构设计能力的程序员

题目描述

设计一个电话目录管理系统，让它支持以下操作：

1. get: 分配给用户一个未被使用的电话号码，获取失败请返回 -1
2. check: 检查指定的电话号码是否可用
3. release: 释放掉一个电话号码，使其能够重新被分配

示例

示例 1：

输入：
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
输出：
[null, 0, 1, true, 2, false, null, true]
解释：
PhoneDirectory phoneDirectory = new PhoneDirectory(3);
phoneDirectory.get();      // 可以返回任意未分配的号码，这里我们假设它返回 0。
phoneDirectory.get();      // 假设，函数返回 1。
phoneDirectory.check(2);   // 号码 2 未分配，所以返回为 true。
phoneDirectory.get();      // 号码 2 已经被分配，所以返回 2。
phoneDirectory.check(2);   // 号码 2 已经被分配，所以返回为 false。
phoneDirectory.release(2); // 释放号码 2，将该号码变回未分配状态。
phoneDirectory.check(2);   // 号码 2 现在是未分配状态，所以返回 true。

提示

• 1 <= maxNumbers <= 10^4
• 0 <= number < maxNumbers
• 调用方法的总次数不超过 20000 次

解题思路

本题可以使用哈希集合和队列解决：

1. 使用哈希集合存储已分配的电话号码
2. 使用队列存储可用的电话号码
3. get操作从队列中取出一个号码
4. check操作检查号码是否在哈希集合中
5. release操作将号码从哈希集合中移除并加入队列

时间复杂度： O(1) 所有操作 空间复杂度： O(n)

图解思路

数据结构设计

数据结构	用途	操作复杂度
HashSet	存储已分配号码	O(1)
Queue	存储可用号码	O(1)

操作流程

操作	步骤	说明
get	1. 从队列取出号码 2. 加入哈希集合	分配新号码
check	检查哈希集合	检查号码状态
release	1. 从哈希集合移除 2. 加入队列	释放号码

代码实现

C# 实现

public class PhoneDirectory {
    private HashSet<int> used;
    private Queue<int> available;
    
    public PhoneDirectory(int maxNumbers) {
        used = new HashSet<int>();
        available = new Queue<int>();
        
        for (int i = 0; i < maxNumbers; i++) {
            available.Enqueue(i);
        }
    }
    
    public int Get() {
        if (available.Count == 0) return -1;
        
        int number = available.Dequeue();
        used.Add(number);
        return number;
    }
    
    public bool Check(int number) {
        return !used.Contains(number);
    }
    
    public void Release(int number) {
        if (used.Contains(number)) {
            used.Remove(number);
            available.Enqueue(number);
        }
    }
}

Python 实现

class PhoneDirectory:
    def __init__(self, maxNumbers: int):
        self.used = set()
        self.available = collections.deque(range(maxNumbers))
        
    def get(self) -> int:
        if not self.available:
            return -1
            
        number = self.available.popleft()
        self.used.add(number)
        return number
        
    def check(self, number: int) -> bool:
        return number not in self.used
        
    def release(self, number: int) -> None:
        if number in self.used:
            self.used.remove(number)
            self.available.append(number)

C++ 实现

class PhoneDirectory {
private:
    unordered_set<int> used;
    queue<int> available;
    
public:
    PhoneDirectory(int maxNumbers) {
        for (int i = 0; i < maxNumbers; i++) {
            available.push(i);
        }
    }
    
    int get() {
        if (available.empty()) return -1;
        
        int number = available.front();
        available.pop();
        used.insert(number);
        return number;
    }
    
    bool check(int number) {
        return used.find(number) == used.end();
    }
    
    void release(int number) {
        if (used.find(number) != used.end()) {
            used.erase(number);
            available.push(number);
        }
    }
};

执行结果

C# 实现

• 执行用时：92 ms
• 内存消耗：24.8 MB

Python 实现

• 执行用时：28 ms
• 内存消耗：13.2 MB

C++ 实现

• 执行用时：4 ms
• 内存消耗：8.4 MB

性能对比

语言	执行用时	内存消耗	特点
C++	4 ms	8.4 MB	执行效率最高，内存占用最小
Python	28 ms	13.2 MB	代码简洁，内存占用适中
C#	92 ms	24.8 MB	类型安全，内存占用较大

代码亮点

1. 🎯 使用哈希集合和队列优化操作
2. 💡 空间复杂度优化
3. 🔍 处理边界情况
4. 🎨 代码结构清晰，易于维护

常见错误分析

1. 🚫 未处理重复释放
2. 🚫 数据结构选择错误
3. 🚫 边界条件处理错误
4. 🚫 并发访问问题

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
哈希集合+队列	O(1)	O(n)	高效，操作简单	空间占用较大
位图	O(1)	O(n/32)	空间优化	实现复杂

相关题目

• LeetCode 380. 常数时间插入、删除和获取随机元素 - 中等
• LeetCode 381. O(1) 时间插入、删除和获取随机元素 - 允许重复 - 困难
• LeetCode 146. LRU缓存机制 - 中等

---

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第379题。

---

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

• 👍 点个赞，让更多人看到这篇文章
• 📁 收藏文章，方便后续查阅复习
• 🔔 关注作者，获取更多高质量算法题解
• 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！