MediumRating 1540

2349. Design a Number Container System

hash-tabledesignheap-priority-queueordered-set

解題說明

Design a Number Container System

題目描述：設計一個數字容器系統，支援兩個操作：change(index, number) 將索引 index 處的數字設為 number（若該索引已有數字則替換）；find(number) 返回包含該數字的最小索引，若不存在則返回 -1。

解題思路：使用兩個映射：

idx2num：記錄每個索引當前對應的數字（用於 change 時清除舊映射）
num2indices：記錄每個數字對應的所有索引集合，使用 set<int>（有序集合）來保證可以快速取得最小索引

當 change(index, number) 時，先從舊數字的集合中移除 index，再將 index 加入新數字的集合。find(number) 直接返回對應集合的第一個元素。

C++ 解法

複雜度分析

時間複雜度：change 為 O(log n)（set 的插入和刪除），find 為 O(1)（取 set 的最小元素） — 其中 n 為索引數量

空間複雜度：O(n) — 儲存所有索引與數字的映射

虛擬碼

1. Maintain two maps:
   - idx2num: index -> current number
   - num2indices: number -> sorted set of indices
2. change(index, number):
   a. If index already has a number, remove index from old number's set
   b. Set idx2num[index] = number
   c. Add index to num2indices[number]
3. find(number):
   a. If num2indices[number] is non-empty, return its minimum element
   b. Otherwise return -1

其他解法

Lazy Heap（懶刪除堆）法：用 priority_queue<int, ..., greater<>> 取代 set 來存放索引。find 時若堆頂的索引已不屬於該數字（延遲刪除），就彈出。平均情況更快但最壞情況可能退化。
有序映射法：使用 map<int, set<int>> 如果還需要按數字順序遍歷。本題只需按索引取最小值，unordered_map + set 的組合效能更佳。

延伸思考

如果還需要支援 findMax(number) 返回包含該數字的最大索引，資料結構需要如何修改？
如果要支援 count(number) 返回包含某數字的索引數量，如何在 O(1) 時間內完成？
如果 change 操作非常頻繁但 find 操作較少，有沒有更適合的資料結構？