981. 基于时间的键值存储
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
TimeMap() 初始化数据结构对象void set(String key, String value, int timestamp) 存储键 key、值 value，以及给定的时间戳 timestamp。String get(String key, int timestamp)
set(key, value, timestamp_prev) 所存储的值，其中 timestamp_prev <= timestamp 。timestamp_prev 的那个值。""）。示例：
输入：
["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" ，时间戳 timestamp = 1
timeMap.get("foo", 1); // 返回 "bar"
timeMap.get("foo", 3); // 返回 "bar", 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值，所以唯一的值位于时间戳 1 处（即 "bar"） 。
timeMap.set("foo", "bar2", 4); // 存储键 "foo" 和值 "bar2" ，时间戳 timestamp = 4
timeMap.get("foo", 4); // 返回 "bar2"
timeMap.get("foo", 5); // 返回 "bar2"
提示：
1 <= key.length, value.length <= 100key 和 value 由小写英文字母和数字组成1 <= timestamp <= 107set 操作中的时间戳 timestamp 都是严格递增的set 和 get 操作 2 * 105 次原站题解
python3 解法, 执行用时: 400 ms, 内存消耗: 71.2 MB, 提交时间: 2022-12-11 09:46:38
# 多行的写法
class TimeMap:
def __init__(self):
"""
Initialize your data structure here.
"""
self.dct = defaultdict(list)
def set(self, key: str, value: str, timestamp: int) -> None:
self.dct[key].append([timestamp, value])
def get(self, key: str, timestamp: int) -> str:
a = bisect_right(self.dct[key], [timestamp, "z"*101])
if a-1 == len(self.dct[key]) or a == 0:
return ""
return (self.dct[key])[a-1][1]
# Your TimeMap object will be instantiated and called as such:
# obj = TimeMap()
# obj.set(key,value,timestamp)
# param_2 = obj.get(key,timestamp)
javascript 解法, 执行用时: 400 ms, 内存消耗: 84 MB, 提交时间: 2022-12-11 09:45:51
var TimeMap = function() {
this.map = new Map();
};
/**
* @param {string} key
* @param {string} value
* @param {number} timestamp
* @return {void}
*/
TimeMap.prototype.set = function(key, value, timestamp) {
if (this.map.has(key)) {
this.map.get(key).push([value, timestamp]);
} else {
this.map.set(key, [[value, timestamp]]);
}
};
/**
* @param {string} key
* @param {number} timestamp
* @return {string}
*/
TimeMap.prototype.get = function(key, timestamp) {
let pairs = this.map.get(key)
if (pairs) {
let low = 0, high = pairs.length - 1;
while (low <= high) {
let mid = Math.floor((high - low) / 2) + low;
if (pairs[mid][1] > timestamp) {
high = mid - 1;
} else if (pairs[mid][1] < timestamp) {
low = mid + 1;
} else {
return pairs[mid][0];
}
}
if (high >= 0) {
return pairs[high][0];
}
return "";
}
return "";
};
/**
* Your TimeMap object will be instantiated and called as such:
* var obj = new TimeMap()
* obj.set(key,value,timestamp)
* var param_2 = obj.get(key,timestamp)
*/
golang 解法, 执行用时: 344 ms, 内存消耗: 67.8 MB, 提交时间: 2022-12-11 09:45:12
type pair struct {
timestamp int
value string
}
type TimeMap struct {
m map[string][]pair
}
func Constructor() TimeMap {
return TimeMap{map[string][]pair{}}
}
func (m *TimeMap) Set(key string, value string, timestamp int) {
m.m[key] = append(m.m[key], pair{timestamp, value})
}
func (m *TimeMap) Get(key string, timestamp int) string {
pairs := m.m[key]
i := sort.Search(len(pairs), func(i int) bool { return pairs[i].timestamp > timestamp })
if i > 0 {
return pairs[i-1].value
}
return ""
}
/**
* Your TimeMap object will be instantiated and called as such:
* obj := Constructor();
* obj.Set(key,value,timestamp);
* param_2 := obj.Get(key,timestamp);
*/
java 解法, 执行用时: 131 ms, 内存消耗: 113 MB, 提交时间: 2022-12-11 09:44:54
class TimeMap {
class Pair implements Comparable<Pair> {
int timestamp;
String value;
public Pair(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
public int hashCode() {
return timestamp + value.hashCode();
}
public boolean equals(Object obj) {
if (obj instanceof Pair) {
Pair pair2 = (Pair) obj;
return this.timestamp == pair2.timestamp && this.value.equals(pair2.value);
}
return false;
}
public int compareTo(Pair pair2) {
if (this.timestamp != pair2.timestamp) {
return this.timestamp - pair2.timestamp;
} else {
return this.value.compareTo(pair2.value);
}
}
}
Map<String, List<Pair>> map;
public TimeMap() {
map = new HashMap<String, List<Pair>>();
}
public void set(String key, String value, int timestamp) {
List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
pairs.add(new Pair(timestamp, value));
map.put(key, pairs);
}
public String get(String key, int timestamp) {
List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
Pair pair = new Pair(timestamp, String.valueOf((char) 127));
int i = binarySearch(pairs, pair);
if (i > 0) {
return pairs.get(i - 1).value;
}
return "";
}
private int binarySearch(List<Pair> pairs, Pair target) {
int low = 0, high = pairs.size() - 1;
if (high < 0 || pairs.get(high).compareTo(target) <= 0) {
return high + 1;
}
while (low < high) {
int mid = (high - low) / 2 + low;
Pair pair = pairs.get(mid);
if (pair.compareTo(target) <= 0) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap obj = new TimeMap();
* obj.set(key,value,timestamp);
* String param_2 = obj.get(key,timestamp);
*/
cpp 解法, 执行用时: 332 ms, 内存消耗: 125.5 MB, 提交时间: 2022-12-11 09:44:29
class TimeMap {
unordered_map<string, vector<pair<int, string>>> m;
public:
TimeMap() {}
void set(string key, string value, int timestamp) {
m[key].emplace_back(timestamp, value);
}
string get(string key, int timestamp) {
auto &pairs = m[key];
// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
pair<int, string> p = {timestamp, string({127})};
auto i = upper_bound(pairs.begin(), pairs.end(), p);
if (i != pairs.begin()) {
return (i - 1)->second;
}
return "";
}
};
/**
* Your TimeMap object will be instantiated and called as such:
* TimeMap* obj = new TimeMap();
* obj->set(key,value,timestamp);
* string param_2 = obj->get(key,timestamp);
*/