981. Time Based Key-Value Store

题目

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.

题目大意

创建一个基于时间的键值存储类 TimeMap，它支持下面两个操作：

set(string key, string value, int timestamp)

存储键 key、值 value，以及给定的时间戳 timestamp。

get(string key, int timestamp)

返回先前调用 set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp。
如果有多个这样的值，则返回对应最大的 timestamp_prev 的那个值。
如果没有值，则返回空字符串（""）。

提示：

所有的键/值字符串都是小写的。
所有的键/值字符串长度都在 [1, 100] 范围内。
所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
1 <= timestamp <= 10^7
TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。

解题思路

要求设计一个基于时间戳的 kv 存储。set() 操作里面会会包含一个时间戳。get() 操作的时候查找时间戳小于等于 timestamp 的 key 对应的 value，如果有多个解，输出满足条件的最大时间戳对应的 value 值。
这一题可以用二分搜索来解答，用 map 存储 kv 数据，key 对应的就是 key，value 对应一个结构体，里面包含 value 和 timestamp。执行 get() 操作的时候，先取出 key 对应的结构体数组，然后在这个数组里面根据 timestamp 进行二分搜索。由于题意是要找小于等于 timestamp 的最大 timestamp ，这会有很多满足条件的解，变换一下，先找 > timestamp 的最小解，然后下标减一即是满足题意的最大解。
另外题目中提到“TimeMap.set 操作中的 timestamp 是严格递增的”。所以在 map 中存储 value 结构体的时候，不需要排序了，天然有序。

Uh oh!

pFad - (p)hone/(F)rame/(a)nonymizer/(d)eclutterfier! Saves Data!