problem:https://leetcode.com/problems/snapshot-array/
这道题暴力做（把所有快照都存下来）会超出空间限制，因此需要减少使用空间，两次快照直接没有改变的值就无需重复记录。可以使用二分搜索，每次修改值的时候记录一下当前快照的值，然后每次查找当前下标特定快照id时的值时，查找小于等于这一快照id对应的值即可。
class SnapshotArray { public: unordered_map<int, map<int, int>> arr; SnapshotArray(int length) { } void set(int index, int val) { arr[index][count] = val; } int count = 0; int snap() { return count++; } int get(int index, int snap_id) { if(arr.find(index) == arr.end()) return 0; auto it = arr[index].upper_bound(snap_id); if(it == arr[index].begin()) { return 0; } return prev(it)->second; } };
[二分搜索] leetcode 1146 Snapshot Array
原文：https://www.cnblogs.com/fish1996/p/11298130.html