leetcode
leetcode 901 ~ 950
基于时间的键值存储

基于时间的键值存储

难度:

标签:

题目描述

代码结果

运行时间: 266 ms, 内存: 66.7 MB


/*
 题目思路:
 使用Java Stream API实现基于时间的键值数据结构。我们仍然使用HashMap存储键和一个TreeMap,其中TreeMap存储时间戳和值。
 set方法添加键值和时间戳,get方法使用stream流查找最大的小于等于给定时间戳的值。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.TreeMap;
import java.util.stream.Collectors;

public class TimeMap {
    private Map<String, TreeMap<Integer, String>> map;

    public TimeMap() {
        map = new HashMap<>();
    }

    public void set(String key, String value, int timestamp) {
        map.computeIfAbsent(key, k -> new TreeMap<>()).put(timestamp, value);
    }

    public String get(String key, int timestamp) {
        if (!map.containsKey(key)) {
            return "";
        }
        return map.get(key).headMap(timestamp + 1).entrySet().stream()
                .max(Map.Entry.comparingByKey())
                .map(Map.Entry::getValue)
                .orElse("");
    }
}

解释

方法:

这个题解使用哈希表加列表的方式来存储键值对和对应的时间戳。对于每个键,哈希表存储一个元组,元组包含两个列表:一个存储时间戳,另一个存储对应的值。当 set 方法被调用时,将时间戳追加到第一个列表,将值追加到第二个列表。当 get 方法被调用时,使用二分查找在时间戳列表中找到小于等于给定时间戳的最大时间戳的位置,然后返回值列表中对应位置的值。如果没有找到,则返回空字符串。

时间复杂度:

set: O(1), get: O(log n)

空间复杂度:

O(n)

代码细节讲解

🦆
为什么选择使用哈希表和列表的组合来实现这个数据结构?是否考虑过其他数据结构的可能性,例如平衡树或者堆?
哈希表和列表组合被选择是因为它们提供了高效的查找和插入性能。使用哈希表可以快速定位到具体的键,而列表用来保持时间戳和值的顺序关系,从而支持高效的时间查询。此外,由于时间戳是单调递增的,列表的末尾插入操作的时间复杂度为O(1)。相比之下,使用平衡树虽然可以在O(log n)时间内完成查找和插入,但实现复杂且常数因子较大。堆结构不适合这种类型的问题,因为堆主要用于维护最大或最小元素,而不是维护一个有序序列供随机访问。
🦆
在使用二分查找时,为什么选择使用`bisect_right`而不是`bisect_left`?这对结果有什么影响?
`bisect_right`函数返回的是插入点后的位置,这意味着返回的索引指向列表中第一个大于给定时间戳的元素位置。在时间戳列表中使用`bisect_right`可以确保我们找到的是小于等于给定时间戳的最大时间戳的正确位置。如果使用`bisect_left`,则可能会得到一个小于指定时间戳的最近时间戳的位置,这在时间戳正好等于列表中某个时间戳时不会返回最正确的结果。因此,使用`bisect_right`更符合这个场景的需求,可以确保即使在多个相同时间戳的情况下也能找到最后一个满足条件的值。

相关问题