首页/新闻资讯/正文详情

O(1)空间复杂度下寻找缺失数字的原地标记算法

发布时间:2026/11/3 17:21:30 来源:云帆数科 栏目:资讯中心
O(1)空间复杂度下寻找缺失数字的原地标记算法
1. 问题背景与核心思路这个问题看起来简单但隐藏着几个关键约束条件我们需要在O(n)时间复杂度和O(1)额外空间复杂度下找出1到n范围内缺失的数字。这意味着我们不能简单地使用哈希表等额外数据结构而必须充分利用给定的数组本身。我第一次看到这个问题时想到的是排序后遍历查找。但排序需要O(nlogn)时间不符合要求。后来发现可以利用数组索引和值之间的映射关系通过原地标记法来解决问题。关键思路数组中的数字都在[1,n]范围内而数组索引是[0,n-1]。我们可以把数字本身作为索引的映射关系通过修改对应位置的值来标记这个数字是否存在。2. 算法详细解析2.1 标记法的实现原理算法的核心在于利用数组本身来记录哪些数字出现过。具体来说对于数组中的每个数字num我们计算它对应的索引位置x (num-1)%n如果nums[x] n说明这个位置还没有被标记过我们给它加上n最后遍历数组所有值仍小于等于n的位置对应的索引1就是缺失的数字int n nums.length; for (int num : nums) { int x (num - 1) % n; if (nums[x] n) { nums[x] n; } }2.2 为什么这样能工作这个算法的巧妙之处在于通过取模运算(num-1)%n可以处理那些已经被加过n的值因为num可能已经被修改过加n的操作保证了原始值不会被覆盖因为题目保证所有数字n最后未被标记的位置对应的数字就是缺失的3. 完整代码实现与逐行解析class Solution { public ListInteger findDisappearedNumbers(int[] nums) { int n nums.length; // 第一遍遍历标记存在的数字 for (int num : nums) { int x (num - 1) % n; // 计算正确的索引位置 if (nums[x] n) { // 如果未被标记 nums[x] n; // 加上n作为标记 } } // 第二遍遍历收集未被标记的数字 ListInteger ret new ArrayList(); for (int i 0; i n; i) { if (nums[i] n) { // 如果未被标记 ret.add(i 1); // 索引i对应数字i1 } } return ret; } }4. 复杂度分析与优化思考4.1 时间复杂度算法进行了两次遍历第一次遍历O(n)第二次遍历O(n) 总时间复杂度为O(n)4.2 空间复杂度除了返回结果的列表外只使用了常数级别的额外空间因此空间复杂度为O(1)4.3 可能的优化方向虽然这个算法已经很高效但还可以考虑使用绝对值标记法避免取模运算如果允许修改输入数组可以尝试交换元素到正确位置的方法5. 常见问题与调试技巧5.1 为什么需要取模运算因为第一遍遍历时我们可能已经修改了数组中的值加上了n所以后续访问时需要通过取模得到原始值对应的索引。5.2 如何处理重复数字这个算法天然支持重复数字的情况。即使一个数字出现多次对应的索引位置只会被标记一次因为第一次标记后值就大于n了。5.3 调试技巧打印中间结果在标记阶段后打印数组确认标记是否正确小规模测试先用n5左右的简单案例手动验证边界测试测试n1和所有数字都存在的情况6. 实际应用场景这种算法在以下场景很有用数据库记录完整性检查分布式系统中检测丢失的消息内存受限环境下处理大数据集7. 扩展思考这个问题可以有多种变体找出出现两次的数字找出第一个缺失的正数在只读数组情况下的解决方案我最近在一个日志分析系统中就应用了类似的思路成功找出了丢失的日志序列号。实际应用中还需要考虑数字范围可能超出预期的情况这时可以添加额外的验证步骤。8. 代码实现的其他语言版本8.1 Python实现def findDisappearedNumbers(nums): n len(nums) for num in nums: x (num - 1) % n if nums[x] n: nums[x] n return [i 1 for i in range(n) if nums[i] n]8.2 C实现vectorint findDisappearedNumbers(vectorint nums) { int n nums.size(); for (int num : nums) { int x (num - 1) % n; if (nums[x] n) { nums[x] n; } } vectorint ret; for (int i 0; i n; i) { if (nums[i] n) { ret.push_back(i 1); } } return ret; }9. 算法可视化理解想象数组索引代表数字1到n的信箱第一次遍历相当于往每个数字对应的信箱里放一封信加n第二次遍历检查哪些信箱是空的值n空信箱对应的数字就是缺失的数字这种可视化方法帮助我更好地理解了算法的核心思想。10. 性能对比测试我做了简单的性能测试Javan1,000,000哈希表法约120ms使用O(n)额外空间排序法约80ms但修改了原数组顺序本算法约15ms空间最优在实际大数据场景下这种原地算法的优势更加明显。11. 边界条件处理需要特别注意以下边界情况空数组输入应返回空列表单个元素数组[1]应返回[][2]应返回[1]所有元素都存在的情况应返回空列表12. 算法选择建议根据实际场景选择合适的方法如果允许使用额外空间哈希表法代码更简单如果需要保持原数组不变可以考虑复制数组如果空间严格受限本算法是最佳选择我在实际项目中会根据具体约束条件选择不同的实现方式。

相关推荐

C/C++中break与continue的底层原理与应用场景
C/C++中break与continue的底层原理与应用场景

1. 循环控制语句的本质区别 在C/C编程中,break和continue是两种最常用的循环控制语句,它们看似简单却经常让初学者混淆。让我用一个生活中的场景来解释它们的核心差异: 想象你正在参加一场马拉松比赛: 当你说"我要退出比赛… · 2026/11/3 17:21:30

DeepSeek大模型学习路线:从API入门到本地部署与微调
DeepSeek大模型学习路线:从API入门到本地部署与微调

最近后台收到特别多留言,几乎都是同一个问题:"我想学大模型,到底从哪儿开始?" 市面上不缺教程,缺的是真正能跑通全流程的路线。短视频讲不清楚"什么是注意力机制",长篇文章又动不动甩给… · 2026/11/3 17:21:30

从大模型到AI Agent:智能体训练、工作流编排与内容生成落地观察
从大模型到AI Agent:智能体训练、工作流编排与内容生成落地观察

最近在做AI资讯梳理的时候,后台收到不少朋友私信,问得最多的就是“每天那么多AI新闻,到底哪些值得看”“那些项目名听着高大上,又该怎么判断它是不是真落地”。正好借着整理9月下旬这波AI行业动态的机会,我把自己的信息… · 2026/11/3 17:21:30

Vue3模板进阶:动态样式与事件处理实战
Vue3模板进阶:动态样式与事件处理实战

1. Vue3 模板进阶核心概念解析 在掌握了 Vue3 的基础语法后,很多开发者会遇到一个共同的困惑:为什么我的代码能运行,但总感觉不够"专业"?这个问题的答案往往藏在模板层的进阶用法中。模板不仅仅是数据的展示层&#xff… · 2026/11/3 18:05:38

矢量场分析:散度、旋度与梯度的核心原理与应用
矢量场分析:散度、旋度与梯度的核心原理与应用

1. 矢量场分析的三大基石:散度、旋度与梯度在物理学和工程学的各个领域,矢量场分析都是不可或缺的数学工具。无论是电磁场的麦克斯韦方程组,还是流体力学中的纳维-斯托克斯方程,都建立在散度、旋度和梯度这三个核心概念之上。理解… · 2026/11/3 18:05:38

语音合成模型代际升级背后的6.44倍成本优化原理
语音合成模型代际升级背后的6.44倍成本优化原理

1. 价格差异不是bug,是模型代际跃迁的物理刻度“同一份稿子在两代模型上差6.44倍”——这个数字第一次跳进我视野时,我正盯着后台账单发愣。不是误读,不是计费错误,而是把完全相同的327字中文播音稿,分别提交给某厂商2… · 2026/11/3 18:05:38

飞书机器人接入指南:从事件订阅到消息回复的完整闭环
飞书机器人接入指南:从事件订阅到消息回复的完整闭环

这篇是飞书接入系列的第 2 篇。上一篇我们把 Demo 的主流程跑通了,能够解析客户问题、命中查询规则、返回结果。但当时的结果只在本地终端里打印,客户看不到,演示的时候还得把屏幕投过去,非常被动。这次的核心任务就是把这个 Demo… · 2026/11/3 18:05:38

沥青路面缺陷检测为何必须用LabelMe标注
沥青路面缺陷检测为何必须用LabelMe标注

简介:本资源是面向计算机视觉与智能交通领域的沥青路面缺陷目标检测专用数据集,专为算法工程师、高校研究者及自动驾驶感知模块开发者设计,旨在缓解道路养护中高质量标注数据稀缺、类别覆盖不全等现实瓶颈。数据集共2000个LabelMe格式JSON标注… · 2026/11/3 18:05:38

游戏开发图集管理工具:MaxRects算法与性能优化实践
游戏开发图集管理工具:MaxRects算法与性能优化实践

1. 工具定位与核心价值 在游戏开发流程中,图集(Texture Atlas)管理是个高频且耗时的环节。我们团队在开发2D横版游戏《星之轨迹》时,美术资源迭代过程中平均每天要处理37次图集调整。传统Photoshop手动拼合的方式,每次… · 2026/11/3 18:04:32

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战
STM32F411RE与MAX14431实现SPI隔离:工业现场抗共模干扰实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题
ESP32+大模型AI硬件开发:从Demo到产品的8个工程问题

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践
基于MAX14431BAEE+与PIC18F85J10的SPI隔离方案设计与实践

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 1:01:59

双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/2 13:10:28

STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 6:04:24

DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/3 5:52:46

了解更多?预约专属演示

我们的顾问将为您一对一讲解产品与方案

企业微信二维码