D.二分查找-进阶——981. 基于时间的键值存储

题目链接：981. 基于时间的键值存储（中等）

算法原理：

解法一：TreeMap

150ms击败58.54%

时间复杂度O(log m)（单次set、get）

1. 存储结构设计
①外层用 HashMap<String, TreeMap<Integer, String>>，HashMap 负责通过 key 快速定位，时间复杂度 O(1)

②内层用 TreeMap，以时间戳为键、值为value，利用 TreeMap 红黑树的特性，自动按时间戳升序存储数据

2. set方法逻辑

①对传入的 key，用 computeIfAbsent 方法：存在则获取对应 TreeMap，不存在则新建 TreeMap 存入 HashMap

②将 <timestamp, value> 存入内层 TreeMap，自动完成排序，时间复杂度 O(log m)（m 为该 key 下的时间戳数量）

3. get方法逻辑

①通过 key 获取对应 TreeMap，无则返回空 TreeMap

②调用 TreeMap 的 floorEntry(timestamp) 方法，直接获取小于等于目标时间戳的最大时间戳对应的键值对

③有结果则返回 value，无结果则返回空字符串，查询时间复杂度 O(log m)

解法二：二分查找

131ms击败89.92%

时间复杂度O(log m)（单次set、get）

1. 存储结构设计
①外层使用HashMap<String, List<Pair>>：key为字符串键，通过key快速定位到对应的Pair列表（时间复杂度O(1)）

②内层List<Pair>：每个Pair封装时间戳和对应值，利用set方法传入的时间戳严格递增特性，列表天然按时间戳升序排列，无需额外排序

2. set方法逻辑

①根据key从HashMap中获取Pair列表，若不存在则新建空列表

②新建Pair对象（封装当前时间戳和值），追加到列表尾部（保持升序）

③将更新后的列表放回HashMap中，完成存储

3. get方法逻辑

①根据key获取Pair列表，若列表为空，直接返回空字符串

②采用最右端点二分模型：在升序列表中，通过二分查找找到最大的满足时间戳≤目标时间戳的元素下标

③判断该下标对应的元素时间戳是否≤目标值：若是，返回对应值；若否（所有元素时间戳都大于目标值），返回空字符串

Java代码：

class TimeMap { //存<字符串键，<时间戳，数值>>Tree会天然按时间戳升序排序 Map<String, TreeMap<Integer, String>> 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) { //获取key对应的TreeMap，如果不存在就默认一个空的TreeMap，避免空指针 //floorEntry(timestamp)：TreeMap的核心方法，返回<=timestamp的最大键对应的键值对Entry Map.Entry<Integer, String> entry = map.getOrDefault(key, new TreeMap<>()).floorEntry(timestamp); return entry == null ? "" : entry.getValue(); } } /** * 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); */

class Pair{ int timestamp; String value; //构造函数，构建一个Pair public Pair(int timestamp,String value){ this.timestamp=timestamp; this.value=value; } } class TimeMap { Map<String,List<Pair>> hash; public TimeMap() { this.hash=new HashMap<String,List<Pair>>(); } //一个hash，键值是key，通过key找到Pair集合（类似TreeMap）,根据Pair集合的时间戳找到目标值 //因为timestamp递增的特性，所以天然升序排序（无需排序再二分） public void set(String key, String value, int timestamp) { Pair pair=new Pair(timestamp,value); List<Pair> pairs=hash.getOrDefault(key,new ArrayList<Pair>()); pairs.add(pair);//追加到key的后面 hash.put(key,pairs);//重新放进哈希表 } public String get(String key, int timestamp) { List<Pair> pairs=hash.getOrDefault(key,new ArrayList<Pair>()); if(pairs.isEmpty()) return ""; //找已存的最大的timestamp,求最右端点模型 int left=0,right=pairs.size()-1; while(left<right){ int mid=left+(right-left+1)/2; //这里的get是List内置的，不是Pair的 //pairs.get(mid)含义：获取pairs列表中，下标为mid的那个Pair对象 if(pairs.get(mid).timestamp>timestamp) right=mid-1; else left=mid; } if(pairs.get(left).timestamp<=timestamp) return pairs.get(left).value; //前一个if没走，说明所有元素都大于timestamp,就是说都是在该时间戳之后set新添的元素，目前这个时间戳还没set过 return ""; } } /** * 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); */