981. Time Based Key-Value Store

置顶

Created At : 2023-10-28 15:14

Count:858 Views 👀 :

Comment:

Create a timebased key-value store class TimeMap, that supports two operations.

1. set(string key, string value, int timestamp)

Stores the key and value, along with the given timestamp.

2. get(string key, int timestamp)

Returns a value such that set(key, value, timestamp_prev) was called previously, with timestamp_prev <= timestamp.
If there are multiple such values, it returns the one with the largest timestamp_prev.
If there are no values, it returns the empty string ("").

Example 1:

Input: inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]
Output: [null,null,"bar","bar",null,"bar2","bar2"]
Explanation: TimeMap kv;  
kv.set("foo", "bar", 1); // store the key "foo" and value "bar" along with timestamp = 1  
kv.get("foo", 1);  // output "bar"  
kv.get("foo", 3); // output "bar" since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 ie "bar"  
kv.set("foo", "bar2", 4);  
kv.get("foo", 4); // output "bar2"  
kv.get("foo", 5); //output "bar2"

Example 2:

Input: inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
Output: [null,null,null,"","high","high","low","low"]

Note:

All key/value strings are lowercase.
All key/value strings have length in the range [1, 100]
The timestamps for all TimeMap.set operations are strictly increasing.
1 <= timestamp <= 10^7
TimeMap.set and TimeMap.get functions will be called a total of 120000 times (combined) per test case.

这道题让我们实现一种基于时间的键值对儿数据结构，有两种操作 set 和 get，其中 set 就是存入键值对儿，同时需要保存时间戳，get 就是查找值，但此时不仅提供了 key 值，还提供了查询的时间戳，返回值的时间戳不能大于查询的时间戳，假如有多个相同值，返回时间戳最大的那个，若查询不到就返回空。实际上这道题考察的就是较为复杂一些的数据结构，因为要同时保存三个量，而且还要提供快速查询功能，可以使用 Map of Maps 的数据结构，外层可以使用一个 HashMap，因为对于 key 值没有顺序要求，而内层要使用一个 TreeMap，因为时间戳的顺序很重要。在 set 函数中直接将数据插入数据结构中，在 get 中，用一个 upper_bound 来进行快速查找第一个大于目标值的位置，往后退一位，就是不大于目标值的位置。但是在退之前要判断得到的位置是否是起始位置，是的话就没法再往前退一位了，直接返回空串，不是的话可以退一位并返回即可，参见代码如下：

class TimeMap {
public:
    TimeMap() {}
    
    void set(string key, string value, int timestamp) {
        dataMap[key].insert({timestamp, value});
    }
    
    string get(string key, int timestamp) {
        auto it = dataMap[key].upper_bound(timestamp);
        return it == dataMap[key].begin() ? "" : prev(it)->second;
    }

private:
    unordered_map<string, map<int, string>> dataMap;
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/981

参考资料：

https://leetcode.com/problems/time-based-key-value-store/

https://leetcode.com/problems/time-based-key-value-store/discuss/226663/TreeMap-Solution-Java

https://leetcode.com/problems/time-based-key-value-store/discuss/226664/C%2B%2B-3-lines-hash-map-%2B-map

LeetCode All in One 题目讲解汇总(持续更新中…)

转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com