二分查找题目：快照数组

题目

标题和出处

标题：快照数组

出处：1146. 快照数组

难度

7 级

题目描述

要求

实现支持下列接口的快照数组：

• $\text{SnapshotArray(int length)}$ 使用给定长度初始化一个类数组的数据结构。初始时，每个元素都等于 $\text{0}$。
• $\text{void set(index, val)}$ 将给定的 $\text{index}$ 处的元素设置为 $\text{val}$。
• $\text{int snap()}$ 获取该数组的快照，并返回快照的编号 $\text{snap\_id}$，快照编号是调用 $\text{snap()}$ 的总次数减 $\text{1}$。
• $\text{int get(index, snap\_id)}$ 根据给定的 $\text{snap\_id}$ 选择快照，返回该快照在给定的 $\text{index}$ 的值。

示例

示例 1：

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

数据范围

• $\text{1}\le \text{length}\le \text{50000}$
• 题目最多调用 $\text{set}$、$\text{snap}$ 和 $\text{get}$ 操作 $\text{50000}$ 次
• $\text{0}\le \text{index}<\text{length}$
• $\text{0}\le \text{snap\_id}<调用\text{snap()}的总次数$
• $\text{0}\le \text{val}\le {\text{10}}^{\text{9}}$

解法

思路和算法

初始时快照编号是 $0$。每次调用 $\text{snap}$ 操作获取快照时，将快照编号加 $1$ 并返回更新前的快照编号，因此在整个过程中，快照编号满足非严格单调递增。

对于 $\text{set}$ 操作，在当前快照编号下将快照数组下标 $\text{index}$ 处的元素设为 $\text{val}$。对于 $\text{get}$ 操作，需要找到快照数组下标 $\text{index}$ 在快照编号不超过 $\text{snap\_id}$ 的最新值。为了实现 $\text{set}$ 操作和 $\text{get}$ 操作，需要对快照数组的每个下标维护元素值信息，即每个下标处需要维护一个列表记录每次更新的快照编号和更新后的元素值，列表中的每个元素为快照编号和最新元素值的对，且按照快照编号非严格升序排序。

对于 $\text{set}$ 操作，在下标 $\text{index}$ 处的列表中添加一个元素，该元素为当前快照编号和 $\text{val}$ 的对。

对于 $\text{snap}$ 操作，将快照编号加 $1$，并返回更新前的快照编号。

对于 $\text{get}$ 操作，首先获得下标 $\text{index}$ 处的列表，然后在该列表中使用二分查找得到小于等于 $\text{snap\_id}$ 的最大快照编号的元素，并返回该元素的值。

用 $\text{low}$ 和 $\text{high}$ 分别表示二分查找的下界和上界。由于需要在列表中查找小于等于 $\text{snap\_id}$ 的最大快照编号的元素，因此初始时 $\text{low}$ 等于 $-1$，$\text{high}$ 等于列表的最大下标。每次查找时，取 $\text{mid}$ 为 $\text{low}$ 和 $\text{high}$ 的平均数向上取整，得到列表下标 $\text{mid}$ 处的元素的快照编号并与 $\text{snap\_id}$ 比较，调整查找的下标范围。

• 如果下标 $\text{mid}$ 处的元素的快照编号小于等于 $\text{snap\_id}$，则小于等于 $\text{snap\_id}$ 的最大快照编号所在下标大于等于 $\text{mid}$，因此在下标范围 $[\text{mid},\text{high}]$ 中继续查找。

• 如果下标 $\text{mid}$ 处的元素的快照编号大于 $\text{snap\_id}$，则小于等于 $\text{snap\_id}$ 的最大快照编号所在下标小于 $\text{mid}$，因此在下标范围 $[\text{low},\text{mid}-1]$ 中继续查找。

当 $\text{low}=\text{high}$ 时，查找结束。

• 如果 $\text{low}\ge 0$，则列表下标 $\text{low}$ 处的元素的快照编号即为小于等于 $\text{snap\_id}$ 的最大快照编号，返回列表下标 $\text{low}$ 处的元素的值。

• 如果 $\text{low}<0$，则列表中不存在小于等于 $\text{snap\_id}$ 的快照编号，由于初始时快照数组中的每个元素都等于 $0$，因此返回 $0$。

代码

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;
    }
}

复杂度分析

• 时间复杂度：构造方法的时间复杂度是 $O(\text{length})$，$\text{set}$ 操作和 $\text{snap}$ 操作的时间复杂度是 $O(1)$，$\text{get}$ 操作的时间复杂度是 $O(\log n)$，其中 $\text{length}$ 是快照数组的长度，$n$ 是 $\text{set}$ 操作的次数。构造方法需要创建长度为 $\text{length}$ 的快照数组并初始化，每次 $\text{set}$ 操作获得列表和向列表中添加元素的时间都是 $O(1)$，每次 $\text{snap}$ 操作获得当前快照编号、将快照编号加 $1$ 和返回更新前的快照编号的时间都是 $O(1)$，每次 $\text{get}$ 操作二分查找的时间是 $O(\log n)$。

• 空间复杂度：$O(\text{length}+n)$，其中 $\text{length}$ 是快照数组的长度，$n$ 是 $\text{set}$ 操作的次数。快照数组的长度是 $\text{length}$，共存储 $n$ 个元素，需要 $O(\text{length}+n)$ 的空间。