学习记录：js算法（四十一）： 基于时间的键值存储

基于时间的键值存储

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

• TimeMap() 初始化数据结构对象
• void set(String key, String value, int timestamp) 存储给定时间戳 timestamp 时的键 key 和值 value。
• String get(String key, int timestamp) 返回一个值，该值在之前调用了 set，其中 timestamp_prev <= timestamp 。如果有多个这样的值，它将返回与最大 timestamp_prev 关联的值。如果没有值，则返回空字符串 （“”） 。

示例 1：
输入：
["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"

我的思路
直接题目都没看懂。。。
网上思路
也没看懂

网上思路

class TimeMap {
    constructor() {
        this.map = {};
    }

    set(key, value, timestamp) {
        if (!this.map[key]) {
            this.map[key] = [];
        }
        this.map[key].push({ timestamp, value });
    }

    get(key, timestamp) {
        if (!this.map[key]) {
            return "";
        }

        const values = this.map[key];
        let left = 0;
        let right = values.length - 1;

        // 使用二分查找找到最大时间戳小于等于给定时间戳的值
        while (left <= right) {
            const mid = Math.floor((left + right) / 2);
            if (values[mid].timestamp <= timestamp) {
                left = mid + 1; // 继续查找右边
            } else {
                right = mid - 1; // 查找左边
            }
        }

        // right 现在是最大时间戳小于等于给定时间戳的索引
        if (right >= 0) {
            return values[right].value;
        } else {
            return ""; // 没有找到合适的时间戳
        }
    }
}

讲解

1. 类的构造函数
   this.map: 初始化一个空对象 map，用于存储键值对。每个键将映射到一个数组，该数组包含多个时间戳和对应的值。
2. set 方法
   检查键是否存在: 如果 this.map 中没有该 key，就初始化一个空数组。
   存储值: 将一个对象 { timestamp, value } 添加到该键对应的数组中。这样，每个键可以存储多个值，且每个值都有一个时间戳。
3. get 方法
   • 检查键是否存在: 如果 this.map 中没有该 key，直接返回空字符串 “”。
   • 二分查找:
     • 使用 left 和 right 指针来定义当前查找的范围。
     • 通过计算 mid 来获取中间的索引，比较 values[mid].timestamp 和给定的 timestamp。
     • 如果 values[mid].timestamp 小于或等于 timestamp，则移动 left 指针向右，继续查找更大的时间戳。
     • 否则，移动 right 指针向左，查找更小的时间戳。

• 返回值:
  当查找结束时，right 指针会指向最大时间戳小于等于给定时间戳的索引，如果 right 大于或等于0，则返回对应的值；否则返回空字符串。

总结

一脸懵。。。开始怀疑自己还能否干这一行了

原文地址：https://blog.csdn.net/weixin_48677331/article/details/142441809

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！