java版本
class SnapshotArray {
int id = 0;
List<int[]>[] snapshots;
public SnapshotArray(int length) {
snapshots = new List[length];
for (int i = 0; i < length; i++) {
snapshots[i] = new ArrayList<int[]>();
}
}
public void set(int index, int val) {
snapshots[index].add(new int[]{id, val});
}
public int snap() {
int curr = id;
id++;
return curr;
}
public int get(int index, int snap_id) {
List<int[]> snaplist = snapshots[index];
int low = -1, high = snaplist.size() - 1;
while (low < high) {
int mid = low + (high - low + 1) / 2;
if (snaplist.get(mid)[0] <= snap_id) {
low = mid;
} else {
high = mid - 1;
}
}
return low >= 0 ? snaplist.get(low)[1] : 0;
}
}
c++版本
class SnapshotArray {
public:
int snap_id=0;
unordered_map<int,vector<pair<int,int>>> history;
SnapshotArray(int length) {
}
void set(int index, int val) {
history[index].emplace_back(snap_id,val);
}
int snap() {
return snap_id++;
}
int get(int index, int snap_id) {
auto &h = history[index];
int l = 0, r = h.size()-1, mid,target = snap_id+1;
while(l <= r){
mid = l +((r-l)>>1);
if(h[mid].first < target){
l = mid+1;
}else{
r = mid-1;
}
}
return l-1 >= 0 ? h[l-1].second:0;
}
};