题目
设计一个基于时间的键值数据结构，该结构可以在不同时间戳存储对应同一个键的多个值，并针对特定时间戳检索键对应的值。
实现 TimeMap 类：
TimeMap()初始化数据结构对象void set(String key, String value, int timestamp)存储给定时间戳timestamp时的键key和值value。String get(String key, int timestamp)返回一个值，该值在之前调用了set，其中timestamp_prev <= timestamp。如果有多个这样的值，它将返回与最大timestamp_prev关联的值。如果没有值，则返回空字符串（""）。
示例 1：
输入：
["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次
思路
- 利用哈希表，键为key，值为timestamp和value组成的pair，每次set的时候都在对应的位置插入<timestamp, value>pair。
- 等要get的时候再按对应key的timestamp排序，最后通过二分查找找到最接近的小于等于当前timestamp的timestamp的value。
- 因为每次都排序开销会太大，所以再定义一个判断是否是有序序列的哈希表，如果有序就不用再排序了。
代码实现
class TimeMap {
public:
unordered_map<string, vector<pair<int, string>>> timekey;
unordered_map<string, bool> issorted;
TimeMap() {
}
void set(string key, string value, int timestamp) {
if(timekey.count(key) != 0) {
if(timestamp >= timekey[key].back().first) issorted[key] = true;
else issorted[key] = false;
}
else issorted[key] = true;
timekey[key].push_back(make_pair(timestamp, value));
}
string get(string key, int timestamp) {
if(timekey.count(key)==0) return "";
if(!issorted[key]) {
sort(timekey[key].begin(), timekey[key].end(), [](pair<int, string> a, pair<int, string> b) {
return a.first <= b.first;
});
issorted[key] = true;
}
int left = 0, right = timekey[key].size()-1, ans = timekey[key].size();
while(left <= right) {
int mid = left + (right-left)/2;
if(timekey[key][mid].first <= timestamp) {
left = mid + 1;
ans = mid;
}
else right = mid - 1;
}
if(ans == timekey[key].size()) return "";
return timekey[key][ans].second;
}
};
/**
* 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)。get的时间复杂度由排序的O(nlogn)和二分查找的O(logn)组成，所以总的时间复杂度为O(nlogn)。
- 空间复杂度：O(n)。
官方题解
- 主要有两个优化，第一，emplace_back()比push_back()方法效率更高；第二，直接把两个值赋进去就好，不用做make_pair，这个似乎是自动完成的。另外一点是我没看下面的数据情况，set的timestamp其实是严格递增的，不用排序，那么时间复杂度就是二分查找的O(logn)了。
- 最后就是使用内置函数upper_bound(区间开始, 区间结尾, target)——找上界，返回对应元素迭代器。如果没有找到头，那么再退一步就是小于等于target的值了。
- 既然是内置函数就不再复现了，对应的函数为auto ans = upper_bound(timekey[key].begin(), timekey[key].end(), timestamp); if(ans != timekey.begin()) return (ans-1)->second; return "";