上海cms模板建站,门户网站域名,头像制作网站,个人备案的网站可以做商城981. 基于时间的键值存储 - 力扣#xff08;LeetCode#xff09; 设计一个基于时间的键值数据结构#xff0c;该结构可以在不同时间戳存储对应同一个键的多个值#xff0c;并针对特定时间戳检索键对应的值。 实现 TimeMap 类#xff1a; TimeMap() 初始化数据结构对象void…981. 基于时间的键值存储 - 力扣LeetCode 设计一个基于时间的键值数据结构该结构可以在不同时间戳存储对应同一个键的多个值并针对特定时间戳检索键对应的值。 实现 TimeMap 类 TimeMap() 初始化数据结构对象void set(String key, String value, int timestamp) 存储键 key、值 value以及给定的时间戳 timestamp。String get(String key, int timestamp) 返回先前调用 set(key, value, timestamp_prev) 所存储的值其中 timestamp_prev timestamp 。如果有多个这样的值则返回对应最大的 timestamp_prev 的那个值。如果没有值则返回空字符串。 示例 输入
[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 100key 和 value 由小写英文字母和数字组成1 timestamp 107set 操作中的时间戳 timestamp 都是严格递增的最多调用 set 和 get 操作 2 * 105 次 class TimeMap {//假设key一样//HashMapInteger , String map new HashMapInteger , String();HashMapString,HashMapInteger , String map new HashMapString,HashMapInteger , String();// ArrayListInteger arr new ArrayListInteger();HashMapString,ArrayListInteger arr new HashMapString,ArrayListInteger();public TimeMap() {arr.clear();map.clear();}public void set(String key, String value, int timestamp) {//arr.add(timestamp);//map.put(timestamp,value);if(!map.containsKey(key)) {HashMapInteger , String tmp new HashMapInteger , String();tmp.put(timestamp,value);map.put(key,tmp);} else {map.get(key).put(timestamp,value);}if(!arr.containsKey(key)) {ArrayListInteger tmp new ArrayListInteger();tmp.add(timestamp);arr.put(key,tmp);} else {arr.get(key).add(timestamp);}}public String get(String key, int timestamp) {if(!map.containsKey(key)) return ;ArrayListInteger arr1 arr.get(key);int right arr1.size()-1;int left 0;int mid 0;while(left right) {mid (leftright)/2;if(arr1.get(mid) timestamp) {left mid1;} else if(arr1.get(mid) timestamp) {right mid-1;} else {return map.get(key).get(arr1.get(mid));}}if(left 0) return ;return map.get(key).get(arr1.get(left-1));// int right arr.size()-1;// int left 0;// int mid 0;// while(left right) {// mid (leftright)/2;// if(arr.get(mid) timestamp) {// left mid1;// } else if(arr.get(mid) timestamp) {// right mid-1;// } else {// System.out.println(mid);// System.out.println(------------);// return map.get(arr.get(mid));// }// }// if(left 0) return ;// return map.get(arr.get(left-1));}
}/*** 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);*/ 每日一题今天是中等题。这道题有些难度但主要也是在理解题目上。 首先读题了解到实际上是一个键值对。在java中键值对一般使用map来存储。但是除了key和value还有一个timestamp。所以实际上是需要一个中介的。题目的set函数实际上就是存储键值对的过程。get函数才是获得答案的过程。由于key会不一样如果一开始就上手可能会很复杂我们可以从简单的写起一步一步往上。 先假设只有一个key的情况。那么key是不用存储的。get要找到给定timestamp前的最大数那实际上就是要找timestamp的最大数。最后肯定是要根据找到的这个timestamp来返回值的所以一开始的键值对我们可以用IntegerString。之后用一个arraylist来存储timestamp。题目的数量级是2*105次方如果直接暴力查找大概率过不了。所以需要使用二分改一下条件让其变成可以找到小于等于timestamp的最大数。按博主的写法最后left会是小于等于timestamp最大数的前一个。当然博主的写法如果找到了就会直接返回了。之后只要根据找到的timestamp去map里取值就可以了。 一个key的情况解决了就是多个key的问题了。多个key无非就是用hashmap把一种key的情况包起来。所以一开始存储的两个数据结构都要用hashmap包起来一个key对应一个mapIntegerString和一个arraylist。之后就是修改set函数了如果原本不存在这个key就要新建一个新的mapIntegerString和一个新的arraylist来存储这个key对应的value和timestamp。如果存在直接获取添加即可。再往后就是修改get函数了如果不存在这个key对应的map或arraylist就说明还没有添加进来过直接返回空字符串就行如果存在就按刚才一个的方法去做就可以了。 今天这道题用到了二分的变式还是很有意义的而且能够锻炼大家数据结构使用的熟练度。不过时间复杂度和空间复杂度都很大大家可以去看看题解寻找更快更好的解决方法。
