公司怎样做网站,做网站编辑工作累吗,网站管理问题,温州建设信息网站创建一个基于时间的键值存储类 TimeMap#xff0c;它支持下面两个操作#xff1a;
set(string key, string value, int timestamp)
存储键 key、值 value#xff0c;以及给定的时间戳 timestamp。
get(string key, int timestamp)
返回先前调用 set(key, value, timesta…创建一个基于时间的键值存储类 TimeMap它支持下面两个操作
set(string key, string value, int timestamp)
存储键 key、值 value以及给定的时间戳 timestamp。
get(string key, int timestamp)
返回先前调用 set(key, value, timestamp_prev) 所存储的值其中 timestamp_prev timestamp。 如果有多个这样的值则返回对应最大的 timestamp_prev 的那个值。 如果没有值则返回空字符串。
解题思路
map
使用map记录键值对因为根据时间戳的不同将会产生多个键值对所以value需要用一个列表来保存并且因为时间戳不是连续的所以我们在对应的value上面还要注明时间戳
二分查找
在通过key定位到对应的value列表以后因为所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。所以可以使用二分查找找出满足timestamp_prev timestamp的value
代码 class TimeMap {MapString,ListString[] map;/** Initialize your data structure here. */public TimeMap() {mapnew HashMap();}public void set(String key, String value, int timestamp) {if(!map.containsKey(key))map.put(key,new ArrayList());map.get(key).add(new String[]{String.valueOf(timestamp),value});}public String get(String key, int timestamp) {if(!map.containsKey(key))return ;ListString[] list map.get(key);int l0,rlist.size()-1;if(timestampInteger.parseInt(list.get(0)[0]))return ;//[]while (lr){int mid(r-l)/2l;if(Integer.parseInt(list.get(mid)[0])timestamp){rmid-1;}else lmid1;}return list.get(r)[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);*/
