981-基于时间的键值存储(Time Based Key-Value Store)
发表于：2021-12-03 | 分类： 中等
字数统计: 480 | 阅读时长: 2分钟 | 阅读量：

原文链接: https://leetcode-cn.com/problems/time-based-key-value-store

英文原文

Design a time-based key-value data structure that can store multiple values for the same key at different time stamps and retrieve the key's value at a certain timestamp.

Implement the TimeMap class:

  • TimeMap() Initializes the object of the data structure.
  • void set(String key, String value, int timestamp) Stores the key key with the value value at the given time timestamp.
  • String get(String key, int timestamp) Returns a value such that set was called previously, with timestamp_prev <= timestamp. If there are multiple such values, it returns the value associated with the largest timestamp_prev. If there are no values, it returns "".

 

Example 1:

Input
["TimeMap", "set", "get", "get", "set", "get", "get"]
[[], ["foo", "bar", 1], ["foo", 1], ["foo", 3], ["foo", "bar2", 4], ["foo", 4], ["foo", 5]]
Output
[null, null, "bar", "bar", null, "bar2", "bar2"]

Explanation
TimeMap timeMap = new TimeMap();
timeMap.set("foo", "bar", 1);  // store the key "foo" and value "bar" along with timestamp = 1.
timeMap.get("foo", 1);         // return "bar"
timeMap.get("foo", 3);         // return "bar", since there is no value corresponding to foo at timestamp 3 and timestamp 2, then the only value is at timestamp 1 is "bar".
timeMap.set("foo", "bar2", 4); // store the key "foo" and value "bar2" along with timestamp = 4.
timeMap.get("foo", 4);         // return "bar2"
timeMap.get("foo", 5);         // return "bar2"

 

Constraints:

  • 1 <= key.length, value.length <= 100
  • key and value consist of lowercase English letters and digits.
  • 1 <= timestamp <= 107
  • All the timestamps timestamp of set are strictly increasing.
  • At most 2 * 105 calls will be made to set and get.

中文题目

设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。

实现 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 次

通过代码

高赞题解

哈希表套数组

由于 timestamp 是严格递增，且没有删除 KV 的操作。

我们可以使用哈希表套数组的方式进行实现，从而达到均摊 $O(1)$ 的插入操作和 $O(\log{n})$ 的查询操作。

具体的，为了方便理解，我们可以先建一个 Node 类，类中包含键值对和时间戳信息。

然后使用一个全局哈希表 map 记录某个 key 对应了哪些 Node。其中多个 Node 是以动态数组的形式进行「以 timestamp 升序」存储：

  • set 操作：以 $O(1)$ 的复杂度找到某个 key 对应的数组，利用 timestamp 严格递增的特性，以 $O(1)$ 复杂度将新 Node 加入当前数组尾部；
  • get 操作：以 $O(1)$ 的复杂度找到某个 key 对应的数组，利用 timestamp 严格递增的特性，通过二分以 $O(\log{n})$ 复杂度找到可能符合条件的 Node。

代码：

[]
class TimeMap {
    class Node {
        String k, v; 
        int t;
        Node (String _k, String _v, int _t) {
            k = _k; v = _v; t = _t;
        }
    }
    
    Map<String, List<Node>> map = new HashMap<>();
    public void set(String k, String v, int t) {
        List<Node> list = map.getOrDefault(k, new ArrayList<>());
        list.add(new Node(k, v, t));
        map.put(k, list);
    }
    
    public String get(String k, int t) {
        List<Node> list = map.getOrDefault(k, new ArrayList<>());
        if (list.isEmpty()) return "";
        int n = list.size();
        int l = 0, r = n - 1;
        while (l < r) {
            int mid = l + r + 1 >> 1;
            if (list.get(mid).t <= t) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return list.get(r).t <= t ? list.get(r).v : "";
    }
}
  • 时间复杂度：set 操作的复杂度为 $O(1)$；get 操作的复杂度为 $O(\log{n})$
  • 空间复杂度：$O(n)$

哈希表套树

如果增加 del 操作呢？我们需要做出何种调整？

考虑在原题的基础上，增加一个 String del(String k, int t) 的功能：将严格等于键和时间戳的 KV 对删掉。

由于存在删除 KV 的动作，我们需要将实现从「哈希表套数组」改成「哈希表套树」，这里直接使用基于红黑树实现的 TreeMap 即可。

同时为了验证删除逻辑的正确性，我们在 get 动作发生前，先产生一次随机性的删除，删除后又重新插入。

代码：

[]
class TimeMap {
    class Node {
        String k, v;
        int t;
        Node (String _k, String _v, int _t) {
            k = _k; v = _v; t = _t;
        }
    }

    Map<String, TreeMap<Integer, Node>> map = new HashMap<>();
    public void set(String k, String v, int t) {
        update(k, t);
        TreeMap<Integer, Node> ts = map.getOrDefault(k, new TreeMap<Integer, Node>());
        ts.put(t, new Node(k, v, t));
        map.put(k, ts);
    }

    Node _get(String k, int t) {
        TreeMap<Integer, Node> ts = map.get(k);
        if (ts == null) return null;
        Map.Entry<Integer, Node> entry = ts.floorEntry(t);
        if (entry == null) return null;
        Node node = entry.getValue();
        return node;
    }

    public String get(String k, int t) {
        randomDel();
        Node node = _get(k, t);
        return node != null && node.t <= t ? node.v : "";
    }

    public String del(String k, int t) {
        TreeMap<Integer, Node> ts = map.get(k);
        if (ts == null) return null;
        Map.Entry<Integer, Node> entry = ts.floorEntry(t);
        if (entry == null) return null;
        Node node = entry.getValue();
        if (node != null && node.t == t) {
            ts.remove(t);
            return node.v;
        }
        return "";
    }

    List<String> allInfo = new ArrayList<>(); 
    Random random = new Random();
    // 保存所有的 kt 信息
    void update(String k, int t) {
        String nk = k + "_" + t;
        allInfo.add(nk);
    } 
    // 随机删除，再重新插入，验证代码正确性
    void randomDel() {
        int idx = random.nextInt(allInfo.size());
        String[] ss = allInfo.get(idx).split("_");
        String k = ss[0];
        int t = Integer.parseInt(ss[1]);
        Node node = _get(k, t);
        del(node.k, node.t);
        set(node.k, node.v, node.t);
    }
}
  • 时间复杂度：set 操作的复杂度为 $O(\log{n})$；get 操作会完成随机删除/重新插入/查询的动作，复杂度均为为 $O(\log{n})$，整个 get 的复杂度仍是 $O(\log{n})$（只是常数变大了）
  • 空间复杂度：$O(n)$

最后

如果把解法二中的 randomDel 去掉，在调用次数为 120000 的数量级下，两种实现效率相差不大，而解法二还支持了删除操作。

像这样的 涉及数据结构运用 的 设计类 题目是不是很有意思？

此类题目本身不考察实际的算法，更多的考察选手的「对各种数据结构对应操作的复杂度认识」、「设计能力」和「编码能力」。

更多与此类题目相关的讲解会在 LeetBook 《设计数据结构》 呈现，本 LeetBook 将会和大家将 LC 上所有与「设计」相关的题目都实现一遍，由浅入深，从热门到常规。欢迎获取呀 ~ 🍭🍭🍭

统计信息

通过次数 提交次数 AC比率
21863 41206 53.1%

提交历史

提交时间 提交结果 执行时间 内存消耗 语言
字符串 哈希表 二分查找 设计
上一篇:
980-不同路径 III(Unique Paths III)
下一篇:
982-按位与为零的三元组(Triples with Bitwise AND Equal To Zero)
本文目录
本文目录
    •
    本站总访问量： 次 |
    Copyright © 2020 - 2021 枫奇丶宛南 | Powered by Hexo | Theme Bamboo