Medium

题目描述

设计一个基于时间的键值数据结构，该结构能够在不同时间戳下为同一个键存储多个值，并能在某个时间戳检索键的值。

实现 TimeMap 类：

  • TimeMap() 初始化数据结构对象。
  • void set(String key, String value, int timestamp) 在给定的时间戳 timestamp 存储键 key 和值 value。
  • String get(String key, int timestamp) 返回一个值，该值在之前调用 set，其中 timestamp_prev <= timestamp。如果有多个这样的值，它将返回对应最大的 timestamp_prev 的那个值。如果没有值，则返回空字符串 ""。

示例 1：

输入：
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
输出：
[null, null, "bar", "bar", null, "bar2", "bar2"]

解释：
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // 存储键 "foo" 和值 "bar" ，时间戳为 1
timeMap.get("foo", 1);         // 返回 "bar"
timeMap.get("foo", 3);         // 返回 "bar", 因为在时间戳 3 和 2 处没有对应 foo 的值，所以唯一的值在时间戳 1 处的 "bar"
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳为 4
timeMap.get("foo", 4);         // 返回 "bar2"
timeMap.get("foo", 5);         // 返回 "bar2"

提示：

  • 1 <= key.length, value.length <= 100
  • key 和 value 由小写英文字母和数字组成
  • 1 <= timestamp <= 10^7
  • set 的所有时间戳 timestamp 都是严格递增的
  • 最多调用 set 和 get 操作 2 * 10^5 次

解题思路

这道题要求实现一个基于时间的键值存储系统。核心思路是利用哈希表存储每个键对应的时间戳-值对列表，并使用二分查找快速定位目标时间戳。

数据结构设计：

  • 使用哈希表，键为字符串，值为包含 (timestamp, value) 对的列表
  • 由于题目保证 set 操作的时间戳是严格递增的，每个键对应的时间戳列表天然有序

核心算法：

  1. set 操作：直接将 (timestamp, value) 添加到对应键的列表末尾，时间复杂度 O(1)
  2. get 操作：在对应键的时间戳列表中使用二分查找，找到小于等于目标时间戳的最大时间戳

二分查找细节：

  • 需要找到 timestamp_prev <= timestamp 的最大值
  • 可以使用标准库的 upper_bound 或手动实现二分查找
  • 如果找不到合适的时间戳，返回空字符串

这种方案充分利用了时间戳递增的特性，避免了每次插入时的排序开销，同时通过二分查找保证了高效的查询性能。

代码实现

class TimeMap {
private:
    unordered_map<string, vector<pair<int, string>>> data;
    
public:
    TimeMap() {
        
    }
    
    void set(string key, string value, int timestamp) {
        data[key].push_back({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        if (data.find(key) == data.end()) {
            return "";
        }
        
        auto& vec = data[key];
        int left = 0, right = vec.size() - 1;
        string result = "";
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (vec[mid].first <= timestamp) {
                result = vec[mid].second;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
};

class TimeMap:

    def __init__(self):
        self.data = {}

    def set(self, key: str, value: str, timestamp: int) -> None:
        if key not in self.data:
            self.data[key] = []
        self.data[key].append((timestamp, value))

    def get(self, key: str, timestamp: int) -> str:
        if key not in self.data:
            return ""
        
        arr = self.data[key]
        left, right = 0, len(arr) - 1
        result = ""
        
        while left <= right:
            mid = (left + right) // 2
            if arr[mid][0] <= timestamp:
                result = arr[mid][1]
                left = mid + 1
            else:
                right = mid - 1
        
        return result

public class TimeMap {
    private Dictionary<string, List<(int, string)>> data;

    public TimeMap() {
        data = new Dictionary<string, List<(int, string)>>();
    }
    
    public void Set(string key, string value, int timestamp) {
        if (!data.ContainsKey(key)) {
            data[key] = new List<(int, string)>();
        }
        data[key].Add((timestamp, value));
    }
    
    public string Get(string key, int timestamp) {
        if (!data.ContainsKey(key)) {
            return "";
        }
        
        var list = data[key];
        int left = 0, right = list.Count - 1;
        string result = "";
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (list[mid].Item1 <= timestamp) {
                result = list[mid].Item2;
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return result;
    }
}

var TimeMap = function() {
    this.data = new Map();
};

TimeMap.prototype.set = function(key, value, timestamp) {
    if (!this.data.has(key)) {
        this.data.set(key, []);
    }
    this.data.get(key).push([timestamp, value]);
};

TimeMap.prototype.get = function(key, timestamp) {
    if (!this.data.has(key)) {
        return "";
    }
    
    const arr = this.data.get(key);
    let left = 0, right = arr.length - 1;
    let result = "";
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        if (arr[mid][0] <= timestamp) {
            result = arr[mid][1];
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
setO(1)O(1)
getO(log n)O(1)
总体O(m + n log n)O(mn)

其中 m 是不同键的数量，n 是每个键的平均时间戳数量。

相关题目