什么是网站的自适应苏州网站推广服务

当前位置： 首页 > news >正文

什么是网站的自适应,苏州网站推广服务,广州公司排名前十,网站界面设计形考文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题#xff1a;快照数组 出处#xff1a;1146. 快照数组 难度 7 级 题目描述 要求 实现支持下列接口的快照数组#xff1a; SnapshotArray(int length) \textt… 文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题快照数组 出处1146. 快照数组 难度 7 级 题目描述 要求 实现支持下列接口的快照数组 SnapshotArray(int length) \texttt{SnapshotArray(int length)} SnapshotArray(int length) 使用给定长度初始化一个类数组的数据结构。初始时每个元素都等于 0 \texttt{0} 0。 void set(index, val) \texttt{void set(index, val)} void set(index, val) 将给定的 index \texttt{index} index 处的元素设置为 val \texttt{val} val。 int snap() \texttt{int snap()} int snap() 获取该数组的快照并返回快照的编号 snap_id \texttt{snap_id} snap_id快照编号是调用 snap() \texttt{snap()} snap() 的总次数减 1 \texttt{1} 1。 int get(index, snap_id) \texttt{int get(index, snap_id)} int get(index, snap_id) 根据给定的 snap_id \texttt{snap_id} snap_id 选择快照返回该快照在给定的 index \texttt{index} index 的值。 示例 示例 1 输入 [SnapshotArray,set,snap,set,get] \texttt{[SnapshotArray,set,snap,set,get]} [SnapshotArray,set,snap,set,get] [[3],[0,5],[],[0,6],[0,0]] \texttt{[[3],[0,5],[],[0,6],[0,0]]} [[3],[0,5],[],[0,6],[0,0]] 输出 [null,null,0,null,5] \texttt{[null,null,0,null,5]} [null,null,0,null,5] 解释 SnapshotArray snapshotArr new SnapshotArray(3); \texttt{SnapshotArray snapshotArr new SnapshotArray(3);} SnapshotArray snapshotArr  new SnapshotArray(3); // 初始化一个长度为 3 \texttt{3} 3 的快照数组 snapshotArr.set(0,5); \texttt{snapshotArr.set(0,5);} snapshotArr.set(0,5); // 赋值 array[0] 5 \texttt{array[0] 5} array[0]  5 snapshotArr.snap(); \texttt{snapshotArr.snap();} snapshotArr.snap(); // 获取快照返回 snap_id 0 \texttt{snap_id 0} snap_id  0 snapshotArr.set(0,6); \texttt{snapshotArr.set(0,6);} snapshotArr.set(0,6); snapshotArr.get(0,0); \texttt{snapshotArr.get(0,0);} snapshotArr.get(0,0); // 获取 snap_id 0 \texttt{snap_id 0} snap_id  0 的快照中 array[0] \texttt{array[0]} array[0] 的值返回 5 \texttt{5} 5 数据范围 1 ≤ length ≤ 50000 \texttt{1} \le \texttt{length} \le \texttt{50000} 1≤length≤50000题目最多调用 set \texttt{set} set、 snap \texttt{snap} snap 和 get \texttt{get} get 操作 50000 \texttt{50000} 50000 次 0 ≤ index length \texttt{0} \le \texttt{index} \texttt{length} 0≤indexlength 0 ≤ snap_id 调用  snap() 的总次数 \texttt{0} \le \texttt{snap_id} 调用~\texttt{snap()}~的总次数 0≤snap_id调用 snap() 的总次数 0 ≤ val ≤ 10 9 \texttt{0} \le \texttt{val} \le \texttt{10}^\texttt{9} 0≤val≤109 解法 思路和算法 初始时快照编号是 0 0 0。每次调用 snap \textit{snap} snap 操作获取快照时将快照编号加 1 1 1 并返回更新前的快照编号因此在整个过程中快照编号满足非严格单调递增。 对于 set \textit{set} set 操作在当前快照编号下将快照数组下标 index \textit{index} index 处的元素设为 val \textit{val} val。对于 get \textit{get} get 操作需要找到快照数组下标 index \textit{index} index 在快照编号不超过 snap_id \textit{snap_id} snap_id 的最新值。为了实现 set \textit{set} set 操作和 get \textit{get} get 操作需要对快照数组的每个下标维护元素值信息即每个下标处需要维护一个列表记录每次更新的快照编号和更新后的元素值列表中的每个元素为快照编号和最新元素值的对且按照快照编号非严格升序排序。 对于 set \textit{set} set 操作在下标 index \textit{index} index 处的列表中添加一个元素该元素为当前快照编号和 val \textit{val} val 的对。 对于 snap \textit{snap} snap 操作将快照编号加 1 1 1并返回更新前的快照编号。 对于 get \textit{get} get 操作首先获得下标 index \textit{index} index 处的列表然后在该列表中使用二分查找得到小于等于 snap_id \textit{snap_id} snap_id 的最大快照编号的元素并返回该元素的值。 用 low \textit{low} low 和 high \textit{high} high 分别表示二分查找的下界和上界。由于需要在列表中查找小于等于 snap_id \textit{snap_id} snap_id 的最大快照编号的元素因此初始时 low \textit{low} low 等于 − 1 -1 −1 high \textit{high} high 等于列表的最大下标。每次查找时取 mid \textit{mid} mid 为 low \textit{low} low 和 high \textit{high} high 的平均数向上取整得到列表下标 mid \textit{mid} mid 处的元素的快照编号并与 snap_id \textit{snap_id} snap_id 比较调整查找的下标范围。 如果下标 mid \textit{mid} mid 处的元素的快照编号小于等于 snap_id \textit{snap_id} snap_id则小于等于 snap_id \textit{snap_id} snap_id 的最大快照编号所在下标大于等于 mid \textit{mid} mid因此在下标范围 [ mid , high ] [\textit{mid}, \textit{high}] [mid,high] 中继续查找。 如果下标 mid \textit{mid} mid 处的元素的快照编号大于 snap_id \textit{snap_id} snap_id则小于等于 snap_id \textit{snap_id} snap_id 的最大快照编号所在下标小于 mid \textit{mid} mid因此在下标范围 [ low , mid − 1 ] [\textit{low}, \textit{mid} - 1] [low,mid−1] 中继续查找。
当 low high \textit{low} \textit{high} lowhigh 时查找结束。 如果 low ≥ 0 \textit{low} \ge 0 low≥0则列表下标 low \textit{low} low 处的元素的快照编号即为小于等于 snap_id \textit{snap_id} snap_id 的最大快照编号返回列表下标 low \textit{low} low 处的元素的值。 如果 low 0 \textit{low} 0 low0则列表中不存在小于等于 snap_id \textit{snap_id} snap_id 的快照编号由于初始时快照数组中的每个元素都等于 0 0 0因此返回 0 0 0。
代码 class SnapshotArray {int id 0;Listint[][] snapshots;public SnapshotArray(int length) {snapshots new List[length];for (int i 0; i length; i) {snapshots[i] new ArrayListint;}}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) {Listint[] 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 ( length ) O(\textit{length}) O(length) set \textit{set} set 操作和 snap \textit{snap} snap 操作的时间复杂度是 O ( 1 ) O(1) O(1) get \textit{get} get 操作的时间复杂度是 O ( log ⁡ n ) O(\log n) O(logn)其中 length \textit{length} length 是快照数组的长度 n n n 是 set \textit{set} set 操作的次数。构造方法需要创建长度为 length \textit{length} length 的快照数组并初始化每次 set \textit{set} set 操作获得列表和向列表中添加元素的时间都是 O ( 1 ) O(1) O(1)每次 snap \textit{snap} snap 操作获得当前快照编号、将快照编号加 1 1 1 和返回更新前的快照编号的时间都是 O ( 1 ) O(1) O(1)每次 get \textit{get} get 操作二分查找的时间是 O ( log ⁡ n ) O(\log n) O(logn)。 空间复杂度 O ( length n ) O(\textit{length} n) O(lengthn)其中 length \textit{length} length 是快照数组的长度 n n n 是 set \textit{set} set 操作的次数。快照数组的长度是 length \textit{length} length共存储 n n n 个元素需要 O ( length n ) O(\textit{length} n) O(lengthn) 的空间。