Triển khai lớp TimeMap hỗ trợ:
set(key, value, timestamp): lưu key, value với timestamp
get(key, timestamp): trả về value có timestamp_prev ≤ timestamp lớn nhất, hoặc "" nếu không có
Ví dụ: set("foo","bar",1), get("foo",1)→"bar", get("foo",3)→"bar", set("foo","bar2",4), get("foo",4)→"bar2", get("foo",5)→"bar2".
Giải pháp: dùng unordered_map
Ví dụ
#include <bits/stdc++.h> using namespace std; class TimeMap { public: 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, 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; } }; int 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; }Đầu vào
set("foo","bar",1) get("foo",1) get("foo",3) set("foo","bar2",4) get("foo",4) get("foo",5)Đầu ra
bar bar bar2 bar2