1146.快照数组

【LetMeFly】1146.快照数组：二分查找

力扣题目链接：https://leetcode.cn/problems/snapshot-array/

实现支持下列接口的「快照数组」- SnapshotArray：

• SnapshotArray(int length) - 初始化一个与指定长度相等的 类数组 的数据结构。初始时，每个元素都等于 0。
• void set(index, val) - 会将指定索引 index 处的元素设置为 val。
• int snap() - 获取该数组的快照，并返回快照的编号 snap_id（快照号是调用 snap() 的总次数减去 1）。
• int get(index, snap_id) - 根据指定的 snap_id 选择快照，并返回该快照指定索引 index 的值。

 

示例：

输入：["SnapshotArray","set","snap","set","get"]
     [[3],[0,5],[],[0,6],[0,0]]
输出：[null,null,0,null,5]
解释：
SnapshotArray snapshotArr = new SnapshotArray(3); // 初始化一个长度为 3 的快照数组
snapshotArr.set(0,5);  // 令 array[0] = 5
snapshotArr.snap();  // 获取快照，返回 snap_id = 0
snapshotArr.set(0,6);
snapshotArr.get(0,0);  // 获取 snap_id = 0 的快照中 array[0] 的值，返回 5

 

提示：

• 1 <= length <= 50000
• 题目最多进行50000 次set，snap，和 get的调用 。
• 0 <= index < length
• 0 <= snap_id < 我们调用 snap() 的总次数
• 0 <= val <= 10^9

解题方法：二分查找

我们只需要开辟一个大小为length的数组a，其中a[i]记录下标i的每个历史版本[[快照编号, 值], ...]。

这样，在修改元素时，只需要往a[index]数组中添加一个(snapID, val)，求a[index]的snapId版本时，只需要二分查找出a[index]对应版本时的值即可。

• 时间复杂度：初始化$O(length)$，设置值$O(1)$，快照$O(1)$，查询$O(\log S)$其中$S$是查询时对应元素的赋值次数
• 空间复杂度$O(length + S2)$，其中$S2$是set操作总次数

AC代码

C++

class SnapshotArray {
private:
    vector<vector<pair<int, int>>> a;  // a[i]: i的每个历史版本[[快照编号, 值], ...]
    int snapId;

public:
    SnapshotArray(int length) : a(length), snapId(0) {}
    
    void set(int index, int val) {
        a[index].push_back({snapId, val});
    }
    
    int snap() {
        return snapId++;
    }
    
    int get(int index, int snap_id) {
        vector<pair<int, int>>::iterator it = upper_bound(a[index].begin(), a[index].end(), pair<int, int>{snap_id + 1, -1});
        return it == a[index].begin() ? 0 : prev(it)->second;
    }
};

Python

# from bisect import bisect_right

class SnapshotArray:
    def __init__(self, length: int):
        self.a = [[] for _ in range(length)]
        self.snapId = 0

    def set(self, index: int, val: int) -> None:
        self.a[index].append((self.snapId, val))

    def snap(self) -> int:
        self.snapId += 1
        return self.snapId - 1

    def get(self, index: int, snap_id: int) -> int:
        it = bisect_right(self.a[index], (snap_id + 1, -1))
        return 0 if not it else self.a[index][it - 1][1]

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/138214080