981. 基于时间的键值存储

1. 题目给出要存储的结构是一种key-多value结构，可以利用map，其value使用一种多value的数据结构即可
2. 每个value会有一个timestamp来对应，且根据约束提示，timestamps是严格递增的，因此使用可使用二分timestamp列表来查询对应的value。
3. 可以直接使用TreeMap来存储timestamp-value对，内置排序和搜索功能。
4. 也可以使用List<Pair>列表来存储，因为timestamps是严格递增的，所以不需要排序功能，直接在List中二分搜索即可。

approach 1，Map+TreeMap

class TimeMap {
    Map<String, TreeMap<Integer, String>> map = new HashMap<>();
    public TimeMap() {
    }
    
    public void set(String key, String value, int timestamp) {
        TreeMap<Integer, String> tm = map.getOrDefault(key, new TreeMap<Integer, String>());
        tm.put(timestamp, value);
        map.putIfAbsent(key, tm);
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        TreeMap<Integer, String> tm = map.get(key);
        Map.Entry<Integer, String> entry = tm.floorEntry(timestamp);
        if (entry == null) return "";
        return entry.getValue();
    }
}

approach 2，map+数组二分查找

与方法1逻辑是一样的，只是没有有内置的数据结构，用二分自己去实现。

class TimeMap {
    Map<String, List<Pair<Integer, String>>> map = new HashMap<>();
    public TimeMap() {
    }
    
    public void set(String key, String value, int timestamp) {
        List<Pair<Integer, String>> list = map.getOrDefault(key, new ArrayList<>());
        list.add(new Pair(timestamp, value));
        map.putIfAbsent(key, list);
    }
    
    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }

        List<Pair<Integer, String>> list = map.get(key);
        return binarySearch(list, timestamp);
    }

    private String binarySearch(List<Pair<Integer, String>> list, int t) {
        int n = list.size();
        int left = 0, right = n - 1;
        
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (list.get(mid).getKey() < t) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }

        if (list.get(left).getKey() <= t) {
            return list.get(left).getValue();
        } else if (left - 1 >= 0){
            return list.get(left - 1).getValue();
        } else {
            return "";
        }
    }
}