題目描述:設計一個時間戳鍵值儲存結構,支援以下兩種操作:
set(key, value, timestamp):儲存鍵值對及其對應的時間戳,保證每次 set 呼叫的 timestamp 嚴格遞增。get(key, timestamp):回傳所有時間戳 ≤ timestamp 中,最新(最大時間戳)對應的值。若不存在,回傳空字串。解題思路:由於 set 操作保證時間戳嚴格遞增,對於每個 key,我們可以用一個有序陣列儲存所有 (timestamp, value) 對(按時間戳遞增)。
get 操作需要找到 ≤ 給定 timestamp 的最大時間戳,這正好是二分搜尋的應用場景——在有序陣列中找最後一個不超過目標值的元素(即 upper_bound - 1)。
資料結構設計:使用 unordered_map<string, vector<pair<int,string>>> 儲存資料。每個 key 對應一個按時間戳排序的 (timestamp, value) 向量。
get 操作:使用二分搜尋找到最後一個時間戳 ≤ 目標時間戳的位置,回傳對應的值。可直接使用 upper_bound 找到第一個大於目標的位置,再往前一步即為答案。
時間複雜度:set 操作為 O(1)(均攤,向量末端插入);get 操作為 O(log n),其中 n 是該 key 對應的時間戳記錄數量,對有序陣列執行二分搜尋。
空間複雜度:O(N),其中 N 是所有 set 操作的總次數,每次呼叫 set 都儲存一條記錄。
TimeMap:
store: map from key -> list of (timestamp, value) pairs
set(key, value, timestamp):
1. Append (timestamp, value) to store[key]
get(key, timestamp):
1. If key not in store: return ""
2. Let entries = store[key] // sorted by timestamp (guaranteed by set)
3. Binary search for last entry with timestamp <= given timestamp:
a. lo = 0, hi = len(entries) - 1, result = ""
b. While lo <= hi:
- mid = (lo + hi) / 2
- If entries[mid].timestamp <= timestamp: result = entries[mid].value, lo = mid + 1
- Else: hi = mid - 1
4. Return result使用 std::upper_bound O(log n):利用 STL 的 upper_bound 搭配自定義比較器,找到第一個時間戳嚴格大於目標值的迭代器,再往前一步即為答案。程式碼更簡潔,時間複雜度相同。
使用 std::map<int, string> 作為內層結構 O(log n):以 map<string, map<int,string>> 儲存資料,內層 map 天然有序。get 操作使用 upper_bound(timestamp) 找到插入位置,若迭代器不在最前端則往前一步取值。優點是語意清晰,缺點是 map 的常數開銷比 vector 大。
set 操作的時間戳不再保證遞增(可能亂序插入),資料結構和演算法需要如何調整?delete(key, timestamp) 操作,刪除指定時間戳的記錄?