05 August 2008
基于时间的键值存储，一个key可以对应多个时间，可以输入时间查询
时间复杂度：set 操作的复杂度为 O(1)；get 使用模板二分搜索，操作的复杂度为 O(logn) 空间复杂度：O(n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class TimeMap {
// Use a HashMap to store the key-value pairs along with their timestamps
private Map<String, List<Pair<Integer, String>>> map;
public TimeMap() {
map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
// If the key doesn't exist in the map, create a new list for it
if (!map.containsKey(key)) {
map.put(key, new ArrayList<>());
}
// Add the value and timestamp as a pair to the list associated with the key
map.get(key).add(new Pair<>(timestamp, value));
}
public String get(String key, int timestamp) {
// If the key doesn't exist in the map, return an empty string
if (!map.containsKey(key)) {
return "";
}
// Get the list of value-timestamp pairs for the given key
List<Pair<Integer, String>> values = map.get(key);
// 模板二分搜索 to find the value with the highest timestamp <= given timestamp
int left = 0, right = values.size() - 1;
while (left + 1 < right) {
int mid = left + (right - left) / 2;
if (values.get(mid).getKey() <= timestamp) {
left = mid;
} else {
right = mid;
}
}
// Check the timestamp at the right index
if (values.get(right).getKey() <= timestamp) {
return values.get(right).getValue();
}
// Check the timestamp at the left index
if (values.get(left).getKey() <= timestamp) {
return values.get(left).getValue();
}
// If no valid value is found, return an empty string
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);
*/