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 <= 10^7
• set 操作中的时间戳 timestamp 都是严格递增的
• 最多调用 set 和 get 操作 2 * 10^5 次

解题思路

普通的键值存储，我们都知道使用Map即可。

这道题在普通的key-value基础上增加了timestamp的概念，那么表示我们需要再增加一个维度，来存储timestamp的值。

需要考虑增加的这个维度用什么数据结构，能够更快的set和get。

我们看下get函数的要求：返回满足timestamp_prev <= timestamp条件最大的timestamp_prev。

1. 二分法
   很明显能想到，如果timestamp_prev是有序的，我们需要找到timestamp_prev列表中，第一个比timestamp小的值。可以用二分法来做。

那我们如何更高效保证timestamp_prev列表是有序的呢？

在这道题中，不需要特别保证这一点，因为题目中规定

• set 操作中的时间戳 timestamp 都是严格递增的

如果题目中没有规定timestamp是递增的，我们就需要使用二分的方法，找到对应的timestamp插入的位置。

2. 链表
   不过我发现用从大到小排序的链表来做这道题，不仅不会超时，反而比二分的效果更好。

set：直接在链表头插入，时间复杂度 O(1)
get：从头开始遍历，找到第一个比目标满足 node.timestamp <=timestamp 的节点即可，最差情况时间复杂度是O(n)

方法	set时间复杂度	get时间复杂度
Map+二分法	O(1)	O(logn)
Map+链表	O(1)	O(n)

代码

Map+数组二分

class TimeMap {

    class Node{
        String val;
        int timestamp;

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

    Map<String, List<Node>> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        List<Node> list = map.getOrDefault(key, new ArrayList<>());
        list.add(new Node(value, timestamp));
        map.put(key, list);
    }
    
    public String get(String key, int timestamp) {
        if(map.containsKey(key)){
            List<Node> list = map.get(key);
            int left = 0, right = list.size() - 1;
            while(left < right){
                int mid = (left + right + 1) / 2;
                Node node = list.get(mid);
                if(node.timestamp <= timestamp){
                    left = mid;
                }else{
                    right = mid - 1;
                }
            }
            Node res = list.get(left);
            if(res.timestamp <= timestamp){
                return res.val;
            }else{
                return "";
            }
        }
        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);
 */

Map+链表：

class TimeMap {

    // 按照timestamp从大到小排列
    class ListNode{
        String val;
        int timestamp;
        ListNode next;

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

    Map<String, ListNode> map;

    public TimeMap() {
        map = new HashMap<>();
    }
    
    public void set(String key, String value, int timestamp) {
        if(map.containsKey(key)){
            // 链表最前面存一个dummy node，方便在链表头插入
            ListNode dummy = map.get(key);
            ListNode prev = dummy;
            ListNode cur = dummy.next;
            while(cur != null && cur.timestamp > timestamp){
                cur = cur.next;
            }
            ListNode newNode = new ListNode(value, timestamp);
            prev.next = newNode;
            newNode.next = cur;
        }else{
            ListNode dummy = new ListNode("", Integer.MAX_VALUE);
            dummy.next = new ListNode(value, timestamp);
            map.put(key, dummy);
        }
    }
    
    public String get(String key, int timestamp) {
        if(map.containsKey(key)){
            ListNode dummy = map.get(key);
            ListNode cur = dummy.next;
            while(cur != null && cur.timestamp > timestamp){
                cur = cur.next;
            }
            return cur != null ? cur.val : "";
        }
        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);
 */

总结

这道题的核心，是找到在Map中嵌套什么数据结构，能够快速找到比target小的最大值。

类似于在有序数组中，找到target的插入位置，可以用二分来优化时间复杂度。

二分法模板

根据二分性质, 某一范围的抽象值可划分为两种情况:
case1 : false, ... , false, true, ..., true
最后一个 false 被称为左分界点, 第一个 true 被称为右分界点
case2 : true, ..., true, false, ... , false
最后一个 true 被称为左分界点, 第一个 false 被称为右分界点

模板一
求 case 1 时的右分界点

int l = 左边界, r = 右边界
while(l < r)
{
    int mid = l + r >> 1;   // 右分界点, 向左取整
    if(check(mid)) r = mid; 
    else l = mid + 1;       
}
if(check(l)) return l;      // 查找成功
return -1;                  // -1 定义为查找失败应返回的值

模板二
求 case 2 时的左分界点

int l = 左边界, r = 右边界
while(l < r)
{
    int mid = l + r + 1 >> 1;// 左分界点, 向右取整
    if(check(mid)) l = mid; 
    else r = mid - 1;       
}
if(check(l)) return l;      // 查找成功
return -1;                  // -1 定义为查找失败应返回的值

这道题，明显是case的情况，求左分界点，所以用模板二。