設計一個基於時間的鍵值資料結構，可以儲存同一個 key 在不同 timestamp 的值，並且能查詢在指定 timestamp 或之前最近的值。實作
set(key, value, timestamp)和get(key, timestamp)兩個方法。
Example:
Input: [“TimeMap”, “set”, “get”, “get”, “set”, “get”] > [[], [“foo”,“bar”,1], [“foo”,1], [“foo”,3], [“foo”,“bar2”,4], [“foo”,4]] Output: [null, null, “bar”, “bar”, null, “bar2”]
Intuition
TIP
由於 timestamp 嚴格遞增，每個 key 對應的 (timestamp, value) 列表天然有序，可以用二分搜尋找「不超過指定時間」的最近值。
set操作直接附加到列表尾部（因為 timestamp 遞增）get操作需要找到「timestamp <= 指定時間」的最後一個值，這就是二分搜尋找右邊界
Approaches
1. Linear Search — set / O(n)
- Idea:
get時線性掃描所有時間戳找到最近的 - Time:
setO(1)，getO(n) - Space:
O(n)
Linear Search Code
class TimeMap() {
private val map = mutableMapOf<String, MutableList<Pair<Int, String>>>()
fun set(key: String, value: String, timestamp: Int) {
map.getOrPut(key) { mutableListOf() }.add(Pair(timestamp, value))
}
fun get(key: String, timestamp: Int): String {
val list = map[key] ?: return ""
var result = ""
for ((t, v) in list) {
if (t <= timestamp) result = v
else break
}
return result
}
}⭐ 2. HashMap + Binary Search — set / O(n)
- Idea: 用 HashMap 儲存每個 key 的時間序列，
get時用二分搜尋找右邊界 - Time:
setO(1)，getO(log n) - Space:
O(n)
class TimeMap() {
private val map = mutableMapOf<String, MutableList<Pair<Int, String>>>()
fun set(key: String, value: String, timestamp: Int) {
map.getOrPut(key) { mutableListOf() }.add(Pair(timestamp, value))
}
fun get(key: String, timestamp: Int): String {
val list = map[key] ?: return ""
var left = 0
var right = list.size - 1
var result = ""
while (left <= right) {
val mid = left + (right - left) / 2
if (list[mid].first <= timestamp) {
result = list[mid].second
left = mid + 1
} else {
right = mid - 1
}
}
return result
}
}🔑 Takeaways
- Pattern: 二分搜尋找右邊界（最後一個滿足條件的值）
- Key trick: 當資料自然有序（如遞增的 timestamp）時，直接利用這個特性做二分搜尋，不需要額外排序。這在設計類問題中很常見