3508. Implement Router
解題說明
Implement Router
題目描述:設計一個路由器系統,支援以下操作:(1) addPacket(source, destination, timestamp) — 將封包加入路由器佇列,若該封包(相同 source、destination、timestamp)已存在則拒絕並回傳 false;(2) forwardPacket() — 轉發佇列中最早的封包並回傳其資訊,若佇列為空回傳空陣列;(3) getCount(destination, startTime, endTime) — 查詢在 [startTime, endTime] 時間範圍內送往指定目的地的封包數量。
解題思路:需要同時支援去重、FIFO 轉發、以及按目的地和時間範圍查詢。使用雜湊集合 (set) 儲存三元組 (source, dest, timestamp) 做去重檢查。使用佇列 (queue) 維護 FIFO 順序。對於按目的地查詢,維護一個 map<int, vector<int>>,將每個目的地的 timestamp 按順序存入有序陣列,查詢時用二分搜尋找到 [startTime, endTime] 範圍內的數量。
C++ 解法
複雜度分析
時間複雜度:addPacket O(log n) — 集合插入;forwardPacket O(log n) — 集合刪除;getCount O(log m) — 二分搜尋,m 為該目的地的封包數。
空間複雜度:O(n) — 儲存所有封包的佇列、集合、與目的地時間戳。
虛擬碼
1. Maintain: queue Q for FIFO, set S for dedup, map D[dest] -> sorted timestamps 2. addPacket(src, dest, ts): a. If (src, dest, ts) in S: return false b. Add to S, push to Q, append ts to D[dest] c. Return true 3. forwardPacket(): a. If Q empty: return [] b. Pop front (src, dest, ts), remove from S, return [src, dest, ts] 4. getCount(dest, start, end): a. Binary search D[dest] for lower_bound(start) and upper_bound(end) b. Return count = upper - lower
其他解法
有序集合 (std::multiset):用 multiset<pair<int,int>> 存 (timestamp, dest),支援範圍查詢,但按 dest 過濾需額外遍歷,效率較差。
分桶法:按目的地分桶,每個桶內用有序結構存封包,查詢時直接定位目的地桶再二分搜尋。本質上與主解法相同。
延伸思考
- 如果路由器有記憶體上限,滿了之後需要丟棄最舊的封包,如何修改 addPacket?
- 如果需要支援「撤銷最近一次 forwardPacket」操作,該如何設計?
- 在多執行緒環境下,如何確保這些操作的執行緒安全性?