-
Notifications
You must be signed in to change notification settings - Fork 56
/
TimeMap.java
66 lines (57 loc) · 1.88 KB
/
TimeMap.java
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
58
59
60
61
62
63
64
65
66
package g0901_1000.s0981_time_based_key_value_store;
// #Medium #String #Hash_Table #Binary_Search #Design #Binary_Search_II_Day_16
// #2022_03_31_Time_239_ms_(72.78%)_Space_213.8_MB_(76.88%)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class TimeMap {
private Map<String, List<TimeStampData>> map;
private static class TimeStampData {
int timestamp;
String value;
TimeStampData(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
}
public TimeMap() {
this.map = new HashMap<>();
}
public void set(String key, String value, int timestamp) {
List<TimeStampData> timeStampDataList;
if (!this.map.containsKey(key)) {
timeStampDataList = new ArrayList<>();
timeStampDataList.add(new TimeStampData(timestamp, value));
map.put(key, timeStampDataList);
} else {
this.map.get(key).add(new TimeStampData(timestamp, value));
}
}
public String get(String key, int timestamp) {
if (!this.map.containsKey(key)) {
return "";
}
List<TimeStampData> list = this.map.get(key);
int start = 0;
int end = list.size() - 1;
while (start <= end) {
int mid = start + (end - start) / 2;
if (list.get(mid).timestamp == timestamp) {
return list.get(mid).value;
}
if (timestamp > list.get(mid).timestamp) {
start = mid + 1;
} else {
end = mid - 1;
}
}
return end < 0 ? "" : list.get(end).value;
}
}
/*
* 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);
*/