基于时间的键值存储 图解题解

TimeMap 的 get 到底该返回哪次存的值

TimeMap 干两件事：set(key, value, timestamp) 把一次赋值连同发生的时刻存起来；get(key, timestamp) 返回这个键在不晚于该时刻的最近一次赋的值，没赋过就返回空串。题面里 set("foo","A6",6) 后，get("foo",7) 得 "A6"、get("foo",2) 得 "A1"，都是取该时刻往前最近的一次。同一个键的 timestamp 严格递增地存入。

同一个键查一次就从最新往回翻，慢在哪

get 每查一次，最直接的做法是把这个键的记录从最新往回翻，碰到第一个时间戳不晚于 t 的就停。一个键存了 n 条，查很早的时刻最坏要翻遍全部 n 条，单次查询是 O(n)。key 存得越多、查得越勤越拖不动，可记录本就按时间排好序，逐条翻等于把这份有序扔着不用。

同一个键的时间戳只增不减，正好落进二分的门槛

省下这趟线性翻找，靠题目送的一句保证：同一个键的 timestamp 严格递增。set 按时间先后一条条追加，每个键的记录列表天生按时间戳从小到大排好，不用再排。找「不晚于 t 的最近一次」就是在有序时间戳里找 ≤ t 里最大的那个，有序数组上定位边界值正是二分查找的活：每比一次中点就甩掉一半记录。也因为有序不用自己维护，set 只管往列表尾追加、O(1) 就完事。

中点时间戳和 t 比完，往哪半收、候选怎么留

二分用两个指针 l、r 圈住候选段，起初 l=0、r=n-1，这是两端都算数的闭区间 [l,r]。再备 ans 存最好答案、初值空串。每轮取中点 mid=(l+r)//2，拿 arr[mid] 时间戳和 t 比：≤ t 是合法候选，先记进 ans，可右边也许还有更晚、仍不晚于 t 的，那才算「最近」，于是 l 跳到 mid+1 往右探；> t 太晚，右边只会更晚一起丢，r 退到 mid-1。循环写 while l<=r，l==r 时还剩一格要查。

foo 存了 A1、A6，查 7 和查 2 各走几轮

题面的 foo 按时间戳存两条：0 号 (1,"A1")、1 号 (6,"A6")。查 get("foo",7)：l=0、r=1，mid=0 时间戳 1 ≤ 7，记 ans="A1"、l 到 1；再 mid=1，时间戳 6 ≤ 7，更新 ans="A6"、l 到 2，超过 r，返回 "A6"。查 get("foo",2)：mid=0 时间戳 1 ≤ 2，记 ans="A1"、l 到 1；再 mid=1，时间戳 6 > 2 太晚，r 退到 0，返回 "A1"。

查得比最早那次还早，返回空串别硬凑一个值

单个键 n 条记录，二分把查询压到约 log₂n 次比较，单次 get 是 O(log n)；set 尾部追加 O(1)；空间存下全部 (时间戳, 值) 对，O(总记录数)。坑都在收尾。ans 初值必须空串：查比最早记录还早的时刻，r 被逼到 -1、没记下候选，就返回空串，若返回最小时间戳那条便是硬塞题目没要的值。时间戳 ≤ t 那支别当场 return，右边可能还有仍不晚于 t 的更晚记录，提前收手会拿到偏早的值，记下再往右才对。

Python

class TimeMap:
    def __init__(self):
        self.store = {}            # key -> [(ts, val), ...]
    def set(self, key, value, ts):
        self.store.setdefault(key, []).append((ts, value))
    def get(self, key, ts):
        arr = self.store.get(key, [])
        l, r, ans = 0, len(arr) - 1, ""
        while l <= r:
            mid = (l + r) // 2
            if arr[mid][0] <= ts:       # 合法候选
                ans = arr[mid][1]       # 记下值，往右找更晚的
                l = mid + 1
            else:                       # 太晚，往左
                r = mid - 1
        return ans

C++

class TimeMap {
    unordered_map<string, vector<pair<int,string>>> store;
public:
    void set(string key, string value, int ts) {
        store[key].push_back({ts, value});
    }
    string get(string key, int ts) {
        auto& arr = store[key];
        int l = 0, r = arr.size() - 1; string ans = "";
        while (l <= r) {
            int mid = (l + r) / 2;
            if (arr[mid].first <= ts) { ans = arr[mid].second; l = mid + 1; }
            else r = mid - 1;
        }
        return ans;
    }
};

Java

class TimeMap {
    Map<String, List<int[]>> idx = new HashMap<>();   // ts
    Map<String, List<String>> val = new HashMap<>();  // value
    public void set(String key, String value, int ts) {
        idx.computeIfAbsent(key, k -> new ArrayList<>()).add(new int[]{ts});
        val.computeIfAbsent(key, k -> new ArrayList<>()).add(value);
    }
    public String get(String key, int ts) {
        List<int[]> a = idx.getOrDefault(key, List.of());
        int l = 0, r = a.size() - 1; String ans = "";
        while (l <= r) {
            int mid = (l + r) / 2;
            if (a.get(mid)[0] <= ts) { ans = val.get(key).get(mid); l = mid + 1; }
            else r = mid - 1;
        }
        return ans;
    }
}