Implement a SnapshotArray that supports the following interface:<\/p>\n\n\n\n
SnapshotArray(int length)<\/code> initializes an array-like data structure with the given length. Initially, each element equals 0<\/strong>.<\/li>void set(index, val)<\/code> sets the element at the given index<\/code> to be equal to val<\/code>.<\/li>int snap()<\/code> takes a snapshot of the array and returns the snap_id<\/code>: the total number of times we called snap()<\/code> minus 1<\/code>.<\/li>int get(index, snap_id)<\/code> returns the value at the given index<\/code>, at the time we took the snapshot with the given snap_id<\/code><\/li><\/ul>\n\n\n\nExample 1:<\/strong><\/p>\n\n\n\nInput:<\/strong> [\"SnapshotArray\",\"set\",\"snap\",\"set\",\"get\"]\n[[3],[0,5],[],[0,6],[0,0]]\nOutput:<\/strong> [null,null,0,null,5]\nExplanation: <\/strong>\nSnapshotArray snapshotArr = new SnapshotArray(3); \/\/ set the length to be 3\nsnapshotArr.set(0,5); \/\/ Set array[0] = 5\nsnapshotArr.snap(); \/\/ Take a snapshot, return snap_id = 0\nsnapshotArr.set(0,6);\nsnapshotArr.get(0,0); \/\/ Get the value of array[0] with snap_id = 0, return 5<\/pre>\n\n\n\nConstraints:<\/strong><\/p>\n\n\n\n1 <= length <= 50000<\/code><\/li>- At most
50000<\/code> calls will be made to set<\/code>, snap<\/code>, and get<\/code>.<\/li>0 <= index < length<\/code><\/li>0 <= snap_id < <\/code>(the total number of times we call snap()<\/code>)<\/li>0 <= val <= 10^9<\/code><\/li><\/ul>\n\n\n\nSolution: map + upper_bound<\/strong><\/h2>\n\n\n\nUse a vector to store maps, one map per element.
The map stores {snap_id -> val}, use upper_bound to find the first version > snap_id and use previous version’s value.<\/p>\n\n\n\n
Time complexity:
Set: O(log|snap_id|)
Get: O(log|snap_id|)
Snap: O(1)
Space complexity: O(length + set_calls)<\/p>\n\n\n\n
\nC++<\/h2>\n\n\n\n\/\/ Author: Huahua\nclass SnapshotArray {\npublic:\n SnapshotArray(int length): id_(0), vals_(length) {}\n\n void set(int index, int val) {\n vals_[index][id_] = val;\n }\n\n int snap() { return id_++; }\n\n int get(int index, int snap_id) const {\n auto it = vals_[index].upper_bound(snap_id);\n if (it == begin(vals_[index])) return 0;\n return prev(it)->second;\n }\nprivate:\n int id_;\n vector> vals_;\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
<\/p>\n","protected":false},"excerpt":{"rendered":"
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…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[89],"tags":[251,462],"class_list":["post-5388","post","type-post","status-publish","format-standard","hentry","category-data-structure","tag-design","tag-map","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5388","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=5388"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5388\/revisions"}],"predecessor-version":[{"id":5392,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/5388\/revisions\/5392"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=5388"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=5388"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=5388"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}