981. 基于时间的键值存储

🟠 🔖 设计 哈希表 字符串 二分查找 🔗 力扣open in new window LeetCodeopen in new window

题目

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 <= 10^7
All the timestamps timestamp of set are strictly increasing.
At most 2 * 10^5 calls will be made to set and get.

题目大意

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

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

提示：

1 <= key.length, value.length <= 100
key 和 value 由小写英文字母和数字组成
1 <= timestamp <= 10^7
set 操作中的时间戳 timestamp 都是严格递增的
最多调用 set 和 get 操作 2 * 10^5 次

解题思路

可以使用 哈希表 + 有序数组 + 二分查找 来实现 TimeMap 类：

使用一个哈希表 store，键为 key，值为一个包含时间戳和对应值的数组（即列表中的元素为 [timestamp, value]）。
每次调用 set 时：
- 如果 key 在哈希表中不存在，创建一个新的数组。
- 将 [timestamp, value] 按照时间戳追加到数组末尾（由于时间戳是严格递增的，数组始终有序）。
对于 get 操作：
- 在哈希表中查找 key 对应的数组，若不存在直接返回空字符串。
- 使用二分查找，找到不超过给定 timestamp 的最大时间戳索引，并返回对应的值。
- 如果没有找到，返回空字符串。

复杂度分析

时间复杂度：
- set 操作：平均时间复杂度为 O(1)，仅插入元素。
- get 操作：使用二分查找，时间复杂度为 O(log n)，其中 n 是每个键对应时间戳的个数。
空间复杂度：O(m)，其中 m 为 set 操作的总次数，哈希表存储所有键及其时间戳和值。

代码

class TimeMap {
	constructor() {
		this.store = new Map(); // 哈希表存储 key -> [[timestamp1, value1], [timestamp2, value2], ...]
	}

	set(key, value, timestamp) {
		if (!this.store.has(key)) {
			this.store.set(key, []);
		}
		this.store.get(key).push([timestamp, value]); // 追加到数组末尾
	}

	get(key, timestamp) {
		if (!this.store.has(key)) return ''; // 如果 key 不存在，返回空字符串

		const values = this.store.get(key);

		let res = '';
		let left = 0,
			right = values.length - 1;

		// 二分查找
		while (left <= right) {
			const mid = Math.floor((left + right) / 2);
			if (values[mid][0] <= timestamp) {
				res = values[mid][1];
				left = mid + 1; // 继续向右寻找更大的 timestamp
			} else {
				right = mid - 1; // 缩小右边界
			}
		}

		return res;
	}
}

/**
 * Your TimeMap object will be instantiated and called as such:
 * var obj = new TimeMap()
 * obj.set(key,value,timestamp)
 * var param_2 = obj.get(key,timestamp)
 */

981. 基于时间的键值存储

# 981. 基于时间的键值存储

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

981. 基于时间的键值存储

题目

题目大意

解题思路

复杂度分析

代码

相关题目