資料結構
網路
關係資料庫管理系統 (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 次瀏覽
廣告