数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学基于时间的键值存储 (C++)
假设我们必须创建一个名为 TimeMap 的基于时间的键值存储类，它支持两种操作。
set(string key, string value, int timestamp): 这将存储键、值以及给定的时间戳。
get(string key, int timestamp): 这将返回一个值，使得之前调用了 set(key, value, timestamp_prev)，其中 timestamp_prev <= timestamp。
现在，如果有多个这样的值，它必须返回 timestamp_prev 值最大的那个值。如果没有这样的值，则返回空字符串 ("")。因此，如果我们像下面这样调用函数：
set("foo","bar",1), get("foo",1), get("foo",3), set("foo","bar2",4), set("foo",4), set("foo",5)，则输出将为：[null, “bar”, “bar”, null, “bar2”, “bar2]
为了解决这个问题，我们将遵循以下步骤：
定义一个映射 m
set() 方法将如下所示：
将 (timestamp, value) 插入 m[key]
get() 方法的工作原理如下：
ret := 空字符串
v := m[key]
low := 0 high := v 的大小 – 1
当 low <= high 时
mid := low + (high – low) / 2
如果 v[mid] 的键 <= timestamp，则
ret := v[mid] 的值 并设置 low := mid + 1
否则 high := mid – 1
返回 ret
让我们看看下面的实现以更好地理解：
示例
#include <bits/stdc++.h>
using namespace std;
class TimeMap {
public:
/** Initialize your data structure here. */
unordered_map <string, vector < pair <int, string> > > m;
TimeMap() {
m.clear();
}
void set(string key, string value, int timestamp) {
m[key].push_back({timestamp, value});
}
string get(string key, int timestamp) {
string ret = "";
vector <pair <int, string> >& v = m[key];
int low = 0;
int high = v.size() - 1;
while(low <= high){
int mid = low + (high - low) / 2;
if(v[mid].first <= timestamp){
ret = v[mid].second;
low = mid + 1;
}else{
high = mid - 1;
}
}
return ret;
}
};
main(){
TimeMap ob;
(ob.set("foo","bar",1));
cout << (ob.get("foo", 1)) << endl;
cout << (ob.get("foo", 3)) << endl;
(ob.set("foo","bar2",4));
cout << (ob.get("foo", 4)) << endl;
cout << (ob.get("foo", 5)) << endl;
}输入
Initialize it then call set and get methods as follows:
set("foo","bar",1))
get("foo", 1))
get("foo", 3))
set("foo","bar2",4))
get("foo", 4))
get("foo", 5))输出
bar bar bar2 bar2
更新于：2020年4月30日
662 次浏览
广告