LeetCode刷题【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 <= 100
• key 和 value 由小写英文字母和数字组成
• 1 <= timestamp <= 107
• set 操作中的时间戳 timestamp 都是严格递增的
• 最多调用 set 和 get 操作 2 * 105 次

题解

HashMap配合List的二分查找来找到指定的值。当然也可以用HashMap配合BST二叉搜索树来实现，或者更进一步AVL树，树的搜索表现应当比二分法来得更好些。

不过其实我对这题有点点疑问

1. 看了下timestamp一定是递增的嘛？感觉不应该是恒定递增的，常见的在业务中，并发条件下时间12345和时间12346发起的两个请求，因为网络或者硬件等因素可能是12346的请求先到服务器的，并不能预先假设这个时间一定是递增的。
2. 题目中要求“如果有多个这样的值，则返回对应最大的 timestamp_prev 的那个值”，题目中感觉说的模棱两可，并没有明确说明是对应当前key下的前一个时间的值，还是不限定当前key下的前一个时间的值

先放个二分法查找的在这，配合二叉树的写法回头加上

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class TimeMap {

    class Node {
        String val;
        int timestamp;

        public Node(String val, int timestamp) {
            this.val = val;
            this.timestamp = timestamp;
        }
    }

    HashMap<String, List<Node>> map;

    /** Initialize your data structure here. */
    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        Node node = new Node(value,timestamp);
        if (map.containsKey(key)){
            map.get(key).add(node);
        }else{
            List<Node> list = new ArrayList<>();
            list.add(node);
            map.put(key,list);
        }
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)){
            return "";
        }
        String val = "";
//            for (int i = 0; i < map.get(key).size(); i++) {
//                if (map.get(key).get(i).timestamp <= timestamp){
//                    val = map.get(key).get(i).val;
//                }
//                if (map.get(key).get(i).timestamp > timestamp){
//                    break;
//                }
//            }//直接遍历查找超时了，放弃
        int left = 0, right = map.get(key).size()-1;
        while (left <= right){
            int mid =  (left + right) >> 1;
            if (map.get(key).get(mid).timestamp <= timestamp){
                left = mid + 1;
                val = map.get(key).get(mid).val;
            }else{
                right = mid-1;
            }
        }
        return val;
    }
}