두 가지 작업을 지원하는 TimeMap이라는 시간 기반 키-값 저장소 클래스를 만들어야 한다고 가정합니다.
-
set(string key, string value, int timestamp):주어진 타임스탬프와 함께 키와 값을 저장합니다.
-
get(string key, int timestamp):이전에 timestamp_prev <=timestamp.
로 set(key, value, timestamp_prev)가 호출된 값을 반환합니다.
이제 이러한 값이 여러 개 있으면 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]
가 됩니다.이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
지도 정의
-
set() 메서드는 다음과 같습니다.
-
m[key]
에 (타임스탬프, 값) 삽입
-
-
get() 메서드는 다음과 같이 작동합니다.
-
ret :=빈 문자열
-
v :=m[키]
-
낮음 :=0 및 높음 :=v의 크기 – 1
-
낮음 <=높음
동안-
중간 :=낮음 + (높음 – 낮음) / 2
-
v[mid] <=타임스탬프의 키인 경우
-
ret :=v[mid] 값 및 낮게 설정 :=mid + 1
-
-
그렇지 않으면 높음 :=중간 – 1
-
-
리턴 렛
-
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예
#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