二分查找题目:快照数组
文章目录
- 题目
- 标题和出处
- 难度
- 题目描述
- 要求
- 示例
- 数据范围
- 解法
- 思路和算法
- 代码
- 复杂度分析
题目
标题和出处
标题:快照数组
出处: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≤index<length
- 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} low=high 时,查找结束。
-
如果 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 low<0,则列表中不存在小于等于 snap_id \textit{snap\_id} snap_id 的快照编号,由于初始时快照数组中的每个元素都等于 0 0 0,因此返回 0 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 ( 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(length+n),其中 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(length+n) 的空间。
相关文章:
二分查找题目:快照数组
文章目录 题目标题和出处难度题目描述要求示例数据范围 解法思路和算法代码复杂度分析 题目 标题和出处 标题:快照数组 出处:1146. 快照数组 难度 7 级 题目描述 要求 实现支持下列接口的快照数组: SnapshotArray(int length) \textt…...
深度学习|表示学习|卷积神经网络|参数共享是什么?|07
如是我闻: Parameter Sharing(参数共享)是卷积神经网络(CNN)的一个重要特性,帮助它高效地处理数据。参数共享的本质就是参数“本来也没有变过”。换句话说,在卷积层中,卷积核的参数&…...
基于相机内参推导的透视投影矩阵
基于相机内参推导透视投影矩阵(splatam): M c a m [ 2 ⋅ f x w 0.0 ( w − 2 ⋅ c x ) w 0.0 0.0 2 ⋅ f y h ( h − 2 ⋅ c y ) h 0.0 0 0 f a r n e a r n e a r − f a r 2 f a r ⋅ n e a r n e a r − f a r 0.0 0.0 − 1.0 0.0 ] M_…...
浅析Dubbo 原理:架构、通信与调用流程
一、Dubbo 简介 Dubbo 是阿里巴巴开源的高性能、轻量级的 Java RPC(Remote Procedure Call,远程过程调用)框架,旨在实现不同服务之间的远程通信和调用。在分布式系统中,不同服务可能部署在不同的服务器上,D…...
03垃圾回收篇(D3_垃圾收集器的选择及相关参数)
目录 学习前言 一、收集器的选择 二、GC日志参数 三、垃圾收集相关的常用参数 四、内存分配与回收策略 1. 对象优先在Eden分配 2. 大对象直接进入老年代 3. 长期存活的对象将进入老年代 4. 动态对象年龄判定 5. 空间分配担保 学习前言 本章主要学习垃圾收集器的选择及…...
一、引论,《组合数学(第4版)》卢开澄 卢华明
零、前言 发现自己数数题做的很烂,重新学一遍组合数学吧。 参考卢开澄 卢华明 编著的《组合数学(第4版)》,只打算学前四章。 通过几个经典问题来了解组合数学所研究的内容。 一、幻方问题 据说大禹治水之前,河里冒出来一只乌龟,…...
Vue3+TS 实现批量拖拽文件夹上传图片组件封装
1、html 代码: 代码中的表格引入了 vxe-table 插件 <Tag /> 是自己封装的说明组件 表格列表这块我使用了插槽来增加扩展性,可根据自己需求,在组件外部做调整 <template><div class"dragUpload"><el-dialo…...
二叉树的所有路径(力扣257)
因为题目要求路径是从上到下的,所以最好采用前序遍历。这样可以保证按从上到下的顺序将节点的值存入一个路径数组中。另外,此题还有一个难点就是如何求得所有路径。为了解决这个问题,我们需要用到回溯。回溯和递归不分家,每递归一…...
Python OrderedDict 实现 Least Recently used(LRU)缓存
OrderedDict 实现 Least Recently used(LRU)缓存 引言正文 引言 LRU 缓存是一种缓存替换策略,当缓存空间不足时,会移除最久未使用的数据以腾出空间存放新的数据。LRU 缓存的特点: 有限容量:缓存拥有固定的…...
LabVIEW项目中的工控机与普通电脑选择
工控机(Industrial PC)与普通电脑在硬件设计、性能要求、稳定性、环境适应性等方面存在显著差异。了解这些区别对于在LabVIEW项目中选择合适的硬件至关重要。下面将详细分析这两种设备的主要差异,并为LabVIEW项目中的选择提供指导。 硬件设…...
Ansys Speos | Speos Meshing 网格最佳实践
概述 网格划分是在各种计算应用中处理3D几何的基本步骤: 表面和体积:网格允许通过将复杂的表面和体积分解成更简单的几何元素(如三角形、四边形、四面体或六面体)来表示复杂的表面和体积。 模拟和渲染:网格是创建离散…...
elasticsearch segment数量对读写性能的影响
index.merge.policy.segments_per_tier 是一个配置选项,用于控制 Elasticsearch 中段(segment)合并策略的行为。它定义了在每一层的段合并过程中,允许存在的最大段数量。调整这个参数可以优化索引性能和资源使用。 假设你有一个索…...
全同态加密理论、生态现状与未来展望(中2)
《全同态加密理论、生态现状与未来展望》系列由lynndell2010gmail.com和mutourend2010gmail.com整理原创发布,分为上中下三个系列: 全同态加密理论、生态现状与未来展望(上):专注于介绍全同态加密理论知识。全同态加密…...
鸿蒙UI(ArkUI-方舟UI框架)-开发布局
返回主章节 → 鸿蒙UI(ArkUI-方舟UI框架) 开发布局 1、布局概述 1)布局结构 2)布局元素组成 3)如何选择布局 声明式UI提供了以下10种常见布局,开发者可根据实际应用场景选择合适的布局进行页面开发。 …...
RPC是什么?和HTTP区别?
RPC 是什么?HTTP 是什么? 作为一个程序员,假设我们需要从A电脑的进程发送一段数据到B电脑的进程,我们一般会在代码中使用 Socket 进行编程。 此时,可选性一般就是 TCP 和 UDP 二选一,由于 TCP 可靠、UDP 不…...
Linux C\C++编程-建立文件和内存映射
【图书推荐】《Linux C与C一线开发实践(第2版)》_linux c与c一线开发实践pdf-CSDN博客 《Linux C与C一线开发实践(第2版)(Linux技术丛书)》(朱文伟,李建英)【摘要 书评 试读】- 京东图书 Linu…...
行政纠错——pycorrector学习
pycorrector是一个开源中文文本纠错工具,它支持对中文文本进行音似、形似和语法错误的纠正。此工具是使用Python3进行开发的,并整合了Kenlm、ConvSeq2Seq、BERT、MacBERT、ELECTRA、ERNIE、Transformer等多种模型来实现文本纠错功能。pycorrector官方仓库…...
Go的defer原理
Go 的 defer 原理 defer 是 Go 语言中的一个关键字,用于延迟执行一个函数调用。它通常用于处理资源释放、连接关闭等操作,确保这些操作在函数返回之前执行。 1. 什么是 defer? defer 关键字用于延迟执行一个函数调用,直到包含它…...
Windows 下本地 Docker RAGFlow 部署指南
Windows 下本地 Docker RAGFlow 部署指南 环境要求部署步骤1. 克隆代码仓库2. 配置 Docker 镜像加速(可选)3. 修改端口配置(可选)4. 启动服务5. 验证服务状态6. 访问服务7. 登录系统8. 配置模型8.1 使用 Ollama 本地模型8.2 使用在线 API 服务9. 开始使用10. 常见问题处理端…...
专题三_穷举vs暴搜vs深搜vs回溯vs剪枝_全排列
dfs解决 全排列&子集 1.全排列 link:46. 全排列 - 力扣(LeetCode) 全局变量回溯 code class Solution { public:vector<vector<int>> ans;vector<int> cur;vector<bool> used;vector<vector<int>> permute…...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
Cursor实现用excel数据填充word模版的方法
cursor主页:https://www.cursor.com/ 任务目标:把excel格式的数据里的单元格,按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例,…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
R语言AI模型部署方案:精准离线运行详解
R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...
【HarmonyOS 5 开发速记】如何获取用户信息(头像/昵称/手机号)
1.获取 authorizationCode: 2.利用 authorizationCode 获取 accessToken:文档中心 3.获取手机:文档中心 4.获取昵称头像:文档中心 首先创建 request 若要获取手机号,scope必填 phone,permissions 必填 …...
免费PDF转图片工具
免费PDF转图片工具 一款简单易用的PDF转图片工具,可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件,也不需要在线上传文件,保护您的隐私。 工具截图 主要特点 🚀 快速转换:本地转换,无需等待上…...
Caliper 配置文件解析:fisco-bcos.json
config.yaml 文件 config.yaml 是 Caliper 的主配置文件,通常包含以下内容: test:name: fisco-bcos-test # 测试名称description: Performance test of FISCO-BCOS # 测试描述workers:type: local # 工作进程类型number: 5 # 工作进程数量monitor:type: - docker- pro…...
