学习记录：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，则返回对应的值；否则返回空字符串。

总结

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