LeetCode 981基于时间的键值存储
题目
创建一个基于时间的键值存储类 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"
示例 2：
输入：inputs = ["TimeMap","set","set","get","get","get","get","get"], inputs = [[],["love","high",10],["love","low",20],["love",5],["love",10],["love",15],["love",20],["love",25]]
输出：[null,null,null,"","high","high","low","low"]
提示：
所有的键/值字符串都是小写的。
所有的键/值字符串长度都在 [1, 100] 范围内。
所有 TimeMap.set 操作中的时间戳 timestamps 都是严格递增的。
1 <= timestamp <= 10^7
TimeMap.set 和 TimeMap.get 函数在每个测试用例中将（组合）调用总计 120000 次。
解题思路
哈希+二分查找
题意大概就是给一种数据结构里面存三个类型的数据，分别是String、String和Integer类型，肯定需要用到HashMap这一数据结构，重点是怎么使用？换句话说，就是到底是<String, String>、还是<String,Integer>、或者<String,Integer>。注意第二个和第三个是不一样的。
根据题中的get方法，是将第一个String当做key，然后返回值。所以需要一种新型的Pair类型，很可惜的是，java9才开始支持Pair的类型，所以还得手写Pair类型。
具体的数据结构为HashMap<String,Pair>，String为key，其中Pair是二元组，存放的是timestamp和value。
因为set操作中的时间戳都是严格递增的，所以二元组Pair中也应该是递增的，这样我们可以根据get操作中的key在哈希表中找到对应的二元组列表pairs，然后根据timestamp在pairs中二分查找。我们需要找到的最大不查过timestamp的时间戳，我们可以查找到第一个查过timestamp的二元组下标i，如果i>0说明存在，否则返回空字符串
class TimeMap {
class Pair implements Comparable<Pair> {
int timestamp;
String value;
public Pair(int timestamp, String value) {
this.timestamp = timestamp;
this.value = value;
}
public int hashCode() {
return timestamp + value.hashCode();
}
public boolean equals(Object obj) {
if (obj instanceof Pair) {
Pair pair2 = (Pair) obj;
return this.timestamp == pair2.timestamp && this.value.equals(pair2.value);
}
return false;
}
public int compareTo(Pair pair2) {
if (this.timestamp != pair2.timestamp) {
return this.timestamp - pair2.timestamp;
} else {
return this.value.compareTo(pair2.value);
}
}
}
Map<String, List<Pair>> map;
public TimeMap() {
map = new HashMap<String, List<Pair>>();
}
public void set(String key, String value, int timestamp) {
List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
pairs.add(new Pair(timestamp, value));
map.put(key, pairs);
}
public String get(String key, int timestamp) {
List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>());
// 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置
Pair pair = new Pair(timestamp, String.valueOf((char) 127));
int i = binarySearch(pairs, pair);
if (i > 0) {
return pairs.get(i - 1).value;
}
return "";
}
private int binarySearch(List<Pair> pairs, Pair target) {
int low = 0, high = pairs.size() - 1;
if (high < 0 || pairs.get(high).compareTo(target) <= 0) {
return high + 1;
}
while (low < high) {
int mid = (high - low) / 2 + low;
Pair pair = pairs.get(mid);
if (pair.compareTo(target) <= 0) {
low = mid + 1;
} else {
high = mid;
}
}
return low;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/time-based-key-value-store/solution/ji-yu-shi-jian-de-jian-zhi-cun-chu-by-le-t98o/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
-
先来说下Pair这个类的书写：
class Pair implements Comparable<Pair> { int timestamp; String value; public Pair(int timestamp, String value) { this.timestamp = timestamp; this.value = value; } public int hashCode() { return timestamp + value.hashCode(); } public boolean equals(Object obj) { if (obj instanceof Pair) { Pair pair2 = (Pair) obj; return this.timestamp == pair2.timestamp && this.value.equals(pair2.value); } return false; } public int compareTo(Pair pair2) { if (this.timestamp != pair2.timestamp) { return this.timestamp - pair2.timestamp; } else { return this.value.compareTo(pair2.value); } } }首先是hashCode和equals覆盖方法，这里的hashCode方法计算采用相加的方法，hashCode主要是保证不一样就行，因为timestamp肯定是不同的，所以可以直接相加即可。其次是equals方法，首先判断obj是不是这个类的实例，如果是的话，再判断属性值是否相等。
然后是实现Comparable
的compareTo的接口方法：首先判断timestamp是否相等，如果相等的话，再根据value排序。一句话讲就是首先根据timestamp排序，如果有一样的，再根据value排序。返回的数如果为大于0的数，表示递减。 -
set方法不用赘述，因为都是单纯的add操作。看get和二分查找的代码注释吧。
public String get(String key, int timestamp) { List<Pair> pairs = map.getOrDefault(key, new ArrayList<Pair>()); // 使用一个大于所有 value 的字符串，以确保在 pairs 中含有 timestamp 的情况下也返回大于 timestamp 的位置 Pair pair = new Pair(timestamp, String.valueOf((char) 127)); int i = binarySearch(pairs, pair); if (i > 0) { return pairs.get(i - 1).value; } return ""; } private int binarySearch(List<Pair> pairs, Pair target) { // 相当于在list中查找一个数 int low = 0, high = pairs.size() - 1; // 如果high小于0，表示只有一个元素或者只有两个元素的情况 if (high < 0 || pairs.get(high).compareTo(target) <= 0) { return high + 1; } while (low < high) { //二分法的变形 int mid = (high - low) / 2 + low; Pair pair = pairs.get(mid); //如果pair<targe的话，将mid设置在mid+1； if (pair.compareTo(target) <= 0) { low = mid + 1; } else { high = mid; } } return low; }