Implement a SnapshotArray that supports the following interface:
SnapshotArray(int length)
initializes an array-like data structure with the given length. Initially, each element equals 0.void set(index, val)
sets the element at the givenindex
to be equal toval
.int snap()
takes a snapshot of the array and returns thesnap_id
: the total number of times we calledsnap()
minus1
.int get(index, snap_id)
returns the value at the givenindex
, at the time we took the snapshot with the givensnap_id
Example 1:
Input: ["SnapshotArray","set","snap","set","get"] [[3],[0,5],[],[0,6],[0,0]] Output: [null,null,0,null,5] Explanation: SnapshotArray snapshotArr = new SnapshotArray(3); // set the length to be 3 snapshotArr.set(0,5); // Set array[0] = 5 snapshotArr.snap(); // Take a snapshot, return snap_id = 0 snapshotArr.set(0,6); snapshotArr.get(0,0); // Get the value of array[0] with snap_id = 0, return 5
Constraints:
1 <= length <= 50000
- At most
50000
calls will be made toset
,snap
, andget
. 0 <= index < length
0 <= snap_id <
(the total number of times we callsnap()
)0 <= val <= 10^9
Notes:
The size of the array can be very large, and the query number can also be very large. Thus, updating the entire array for every snapshot is not a good idea.
Instead, we just need to update the element that is changed. And we can store this information in a sorted order relative to the snap_id. And the snap_id is monotonically increases.
After storing this information, for getting the value at a specific snap_id, we just need to do a binary search at that index, since the snap_id is sorted.
To this question, we need to find the upper boundary of the snap_id first, then -1 if it is not 0. The reason to do the upper boundary searching is that, we did not update the snap_id for every element, and only update the one when it is changed.
See the code below:
class SnapshotArray { public: SnapshotArray(int length) { //initialization ct = 0; for(int i=0; i<length; ++i) { ns.push_back(vector<pair<int, int>>{{ct, 0}}); } } void set(int index, int val) { ns[index].push_back({ct, val}); } int snap() { return ct++; } int get(int index, int snap_id) { int ps = help(ns, index, snap_id); if(ps>0) --ps; return ns[index][ps].second; } private: vector<vector<pair<int, int>>> ns; int ct; int help(vector<vector<pair<int, int>>> &ns, int i, int id) { int left = 0, right = ns[i].size(); while(left < right) { int mid = left + (right - left) /2; if(ns[i][mid].first <= id) left = mid + 1; else right = mid; } return left; } }; /** * Your SnapshotArray object will be instantiated and called as such: * SnapshotArray* obj = new SnapshotArray(length); * obj->set(index,val); * int param_2 = obj->snap(); * int param_3 = obj->get(index,snap_id); */
No comments:
Post a Comment