題目網址：https://leetcode.cn/problems/time-based-key-value-store/

題意：設計一個基於時間的 key-value 的資料結構, 它可以在不同 timestamp 儲存對應同一個 key 的多個值, 並針對特定 timestamp 得到相對應的 key 的 value。

實作 TimeMap class：

  • TimeMap() : 初始化 instance
  • void set(String key, String value, int timestamp) : 儲存 key、 value, 以及 timestamp。
  • String get(String key, int timestamp) :
    • 返回 timestamp_prev 對應的 value, 其中 timestamp_prev <= timestamp
    • 如果存在多個值, 則返回對應最大的 timestamp_prev 的 value。
    • 如果不存在, 則返回 ""。

注意: set(key, value, timestamp) 中的 timestamp 都是嚴格遞增的。

Solution：

想法：題目的意思如下圖, key 裡面會儲存 values, 而 values 裡面可以有多個 {value, timestmap} pair。由於 values 裡面的 timestamp 都是嚴格遞增的(已排序), 所以我們可直接使用 Binary Search

class TimeMap {
public:
    TimeMap() {}

    void set(string key, string value, int timestamp) {
        m[key].emplace_back(pair<string, int>{value, timestamp});
    }

    string get(string key, int timestamp) {
        if (m.find(key) == m.end()) {
            return "";
        }

        const int n = m[key].size();
        int left = 0, right = n - 1;

        while (left <= right) {
            const int mid = left + (right - left) / 2;

            if (m[key][mid].second > timestamp) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        // left 為 > timestamp 的位置, 故 left - 1 為 <= timestamp 的位置
        return (left - 1 >= 0) ? m[key][left - 1].first : "";
    }

private:
    unordered_map<string, vector<pair<string, int>>> m;
};
  • time：$O(log(n))$ ➔ Binary Search, 其中 n 為 m[key] 的長度
  • space：$O(n)$ ➔ 其中 n 為 set() 的次數