981. Time Based Key-Value Store

Medium

Description

設計一個基於時間的鍵值資料結構，可以儲存同一個 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#

由於 timestamp 嚴格遞增，每個 key 對應的 (timestamp, value) 列表天然有序，可以用二分搜尋找「不超過指定時間」的最近值。

set 操作直接附加到列表尾部（因為 timestamp 遞增）
get 操作需要找到「timestamp <= 指定時間」的最後一個值，這就是二分搜尋找右邊界

Approaches#

1: Linear Search#

概念: get 時線性掃描所有時間戳找到最近的
時間複雜度: set O(1)，get O(n)
空間複雜度: O(n)

Linear Search 程式碼

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#

概念: 用 HashMap 儲存每個 key 的時間序列，get 時用二分搜尋找右邊界
時間複雜度: set O(1)，get O(log n)
空間複雜度: 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: 二分搜尋找右邊界（最後一個滿足條件的值）
關鍵技巧: 當資料自然有序（如遞增的 timestamp）時，直接利用這個特性做二分搜尋，不需要額外排序。這在設計類問題中很常見