写点什么

【LeetCode】基于时间的键值存储 Java 题解

用户头像
HQ数字卡
关注
发布于: 39 分钟前

题目描述

创建一个基于时间的键值存储类 TimeMap,它支持下面两个操作:


  1. set(string key, string value, int timestamp)


存储键 key、值 value,以及给定的时间戳 timestamp。


2. get(string key, int timestamp)


返回先前调用 set(key, value, timestamp_prev) 所存储的值,其中 timestamp_prev <= timestamp。如果有多个这样的值,则返回对应最大的  timestamp_prev 的那个值。如果没有值,则返回空字符串("")。


示例 1:
输入:inputs = ["TimeMap","set","get","get","set","get","get"], inputs = [[],["foo","bar",1],["foo",1],["foo",3],["foo","bar2",4],["foo",4],["foo",5]]输出:[null,null,"bar","bar",null,"bar2","bar2"]解释: TimeMap kv; kv.set("foo", "bar", 1); // 存储键 "foo" 和值 "bar" 以及时间戳 timestamp = 1 kv.get("foo", 1); // 输出 "bar" kv.get("foo", 3); // 输出 "bar" 因为在时间戳 3 和时间戳 2 处没有对应 "foo" 的值,所以唯一的值位于时间戳 1 处(即 "bar") kv.set("foo", "bar2", 4); kv.get("foo", 4); // 输出 "bar2" kv.get("foo", 5); // 输出 "bar2"
来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/time-based-key-value-store著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
复制代码

思路分析

  • 今天的每日一题是设计类题目,题干比较长,需要认真思考。分析之后,set 操作就是存储 kv 关系, get 就是获取 timestamp 最近的值。

  • 采用 hashmap 结构可以很好的存储上述的关系。

代码

class TimeMap {
/** Initialize your data structure here. */ Map<String, Map<Integer, String>> map; public TimeMap() { map = new HashMap<>(); } public void set(String key, String value, int timestamp) { Map<Integer, String> temp; if (map.containsKey(key)) { temp = map.get(key); } else { temp = new HashMap<>(); } temp.put(timestamp, value);
map.put(key, temp); } public String get(String key, int timestamp) { String ans = ""; if (map.containsKey(key)) { Map<Integer, String> temp = map.get(key); while (timestamp >= 0) { if (temp.containsKey(timestamp)) { ans = temp.get(timestamp); break; } timestamp--; } } return ans; }}


/** * Your TimeMap object will be instantiated and called as such: * TimeMap obj = new TimeMap(); * obj.set(key,value,timestamp); * String param_2 = obj.get(key,timestamp); */
复制代码

总结

  • 上述代码的 set 操作的时间复杂度是 O(1), 空间复杂度是 O(n). get 操作的时间复杂度是 O(n), 空间复杂度是 O(n)。

  • 坚持每日一题,加油!

发布于: 39 分钟前阅读数: 2
用户头像

HQ数字卡

关注

还未添加个人签名 2019.09.29 加入

LeetCode,略懂后端的RD

评论

发布
暂无评论
【LeetCode】基于时间的键值存储Java题解