981. 基于时间的键值存储

题解：宫水三叶

先做HashMap+数组的基本解法和偷鸡解法。后面再看HashMap+树的做法。这里需要注意看题目，题目表明：

​ 所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。

因此可以利用二分查找达成“找到小于等于查询时间戳的最大时间戳的键值”这一要求。

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
class TimeMap {
    class Node {
        String k, v;
        int t;
        Node(String k, String v, int t) {
            this.k = k;
            this.v = v;
            this.t = t;
        }
    }

    Map<String, List<Node>> map = new HashMap<>();
    /** Initialize your data structure here. */
    public TimeMap() {
    }
    
    public void set(String key, String value, int timestamp) {
        List<Node> list = map.getOrDefault(key, new ArrayList<>());
        list.add(new Node(key, value, timestamp));
        map.put(key,list);
    }
    
    public String get(String key, int timestamp) {
        List<Node> list = map.getOrDefault(key, new ArrayList<>());
        if(list.size() == 0) {
            return "";
        }
        int len = list.size();
        int l = 0, r = len - 1;
        while(l < r) {
            int mid = l + r + 1 >> 1;
            if(list.get(mid).t <= timestamp) {
                l = mid;
            }
            else {
                r = mid - 1;
            }
        }
        return list.get(r).t <= timestamp ? list.get(r).v : "";
    }
}

偷鸡做法：floorEntry （从大佬那里抄来学习一下）

1
2
3
4
5
6
7
8
9
10
class TimeMap {
    Map<String, TreeMap<Integer, String>> map = new HashMap<>();
    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }
    public String get(String key, int timestamp) {
        Map.Entry<Integer, String> entry = map.getOrDefault(key, new TreeMap<>()).floorEntry(timestamp);
        return entry == null ? "" : entry.getValue();
    }
}