- Create a timebased key-value store class TimeMap, that supports two operations.
- 1. set(string key, string value, int timestamp)
Stores the key and value, along with the given timestamp.
- 2. get(string key, int timestamp)
- Returns a value such that
- set(key, value, timestamp_prev)
- was called previously, with
- timestamp_prev <= timestamp
- .
- If there are multiple such values, it returns the one with the largest timestamp_prev.
- If there are no values, it returns the empty string ("").
- Runtime: 212 ms, faster than 55.01% of C++ online submissions for Time Based Key-Value Store.
- Memory Usage: 57 MB, Less than 100.00% of C++ online submissions for Time Based Key-Value Store.
- class TimeMap {
- private:
- unordered_map<string, map<int, string>> mp;
- vector<int> tvec;
- public:
- /** Initialize your data structure here. */
- TimeMap() {}
- void set(string key, string value, int timestamp) {
- mp[key][timestamp] = value;
- }
- string get(string key, int timestamp) {
- if(!mp.count(key)) return "";
- if(mp[key].count(timestamp)) return mp[key][timestamp];
- for(auto it = mp[key].rbegin(); it != mp[key].rend(); it++) {
- if(it->first> timestamp) continue;
- else {
- return it->second;
- }
- }
- return "";
- }
- };
来源: http://www.bubuko.com/infodetail-2944816.html