双指针算法解决有序数组去重问题-云帆数科

1. 题目背景与核心需求力扣第80题删除有序数组中的重复项Ⅱ是数组操作类经典题目属于双指针算法的典型应用场景。题目要求在一个非严格递增排列的数组中原地删除重复出现的元素使得每个元素最多出现两次返回删除后数组的新长度。与简单版力扣第26题的区别在于本题允许元素最多重复两次而非完全去重。这种设定更贴近实际开发场景——比如日志系统中需要保留最近两次相同错误记录或用户行为分析中保留关键操作的最近两次触发时间。2. 解题思路分析与算法选择2.1 暴力解法的时间复杂度问题最直观的解法是使用额外数组存储结果遍历原数组时检查当前元素是否已在结果数组中出现两次。但这种方法空间复杂度O(n)不符合原地修改要求每次插入都需要遍历结果数组检查重复次数时间复杂度恶化至O(n²)2.2 双指针算法的优势采用快慢指针可以在O(n)时间、O(1)空间内解决问题慢指针slow指向下一个待写入位置快指针fast遍历数组的当前位置关键判断条件当nums[fast] ! nums[slow-2]时说明当前元素未重复两次以上将nums[fast]写入nums[slow]位置然后slow前移这种解法只需一次遍历且无需额外存储空间完美符合题目要求。3. 详细实现步骤与代码解析3.1 Python标准实现def removeDuplicates(nums): if len(nums) 2: return len(nums) slow 2 for fast in range(2, len(nums)): if nums[fast] ! nums[slow-2]: nums[slow] nums[fast] slow 1 return slow代码要点说明边界处理数组长度≤2时直接返回初始化slow2因为前两个元素无论是否重复都符合要求从fast2开始遍历比较nums[fast]与nums[slow-2]3.2 关键步骤可视化以nums [1,1,1,2,2,3]为例fastslownums状态判断条件操作22[1,1,1,2,2,3]nums[2]nums[0]不写入32[1,1,1,2,2,3]nums[3]!nums[0]nums[2]2, slow343[1,1,2,2,2,3]nums[4]!nums[1]nums[3]2, slow454[1,1,2,2,2,3]nums[5]!nums[2]nums[4]3, slow5最终返回slow5数组前5位为[1,1,2,2,3]4. 边界条件与特殊测试用例4.1 必须考虑的边界情况空数组[]→ 返回0单元素数组[1]→ 返回1双元素相同[1,1]→ 返回2全相同元素[1,1,1,1]→ 返回2无需删除[1,2,3,4]→ 返回44.2 测试用例设计技巧test_cases [ ([], 0), ([1], 1), ([1,1], 2), ([1,1,1], 2), ([1,2,2,2,3,3], 5), ([0,0,1,1,1,1,2,3,3], 7) ]建议在IDE中逐步调试观察指针变化这对理解双指针移动逻辑至关重要。5. 算法优化与变种思考5.1 通用化解决方案将最大重复次数抽象为参数kdef removeDuplicates(nums, k2): if len(nums) k: return len(nums) slow k for fast in range(k, len(nums)): if nums[fast] ! nums[slow-k]: nums[slow] nums[fast] slow 1 return slow5.2 相关题目拓展力扣26题完全去重将k设为1即可力扣27题移除元素双指针变种判断条件改为元素值不等于给定值力扣283题移动零将特定值零移动到末尾的特殊情况6. 常见错误与调试技巧6.1 典型错误模式指针初始化错误错误slow 0→ 会导致前k个元素被错误覆盖正确slow k保留前k个元素的合法性比较对象错误错误比较nums[fast]与nums[slow-1]正确比较nums[fast]与nums[slow-k]边界条件遗漏未处理数组长度小于k的情况未考虑全相同元素的特殊情况6.2 调试建议使用小规模测试用例长度3-5逐步跟踪指针变化打印每次循环后的数组状态print(ffast{fast}, slow{slow}, nums{nums})对特殊用例单独测试特别是全相同和全不同两种情况7. 实际工程应用场景这种去重算法在以下场景有实际应用价值时间序列数据处理传感器数据采集时去除连续重复的异常值股票交易记录中合并连续相同的价格变动日志系统优化合并连续的相同错误日志保留重要操作的最近两次记录数据库操作批量插入前的数据去重处理结果集的后处理优化8. 性能对比与复杂度分析方法时间复杂度空间复杂度是否原地修改暴力解法O(n²)O(n)否哈希表计数O(n)O(n)否双指针本文O(n)O(1)是实测对比100万元素数组双指针约120ms暴力解法超时10s哈希表约450ms因额外空间分配9. 不同语言实现要点9.1 Java实现注意点public int removeDuplicates(int[] nums) { if (nums.length 2) return nums.length; int slow 2; for (int fast 2; fast nums.length; fast) { if (nums[fast] ! nums[slow-2]) { nums[slow] nums[fast]; } } return slow; }特别注意数组长度通过nums.length获取slow实现了先赋值后自增9.2 C实现优化int removeDuplicates(vectorint nums) { const int n nums.size(); if (n 2) return n; int slow 2; for (int fast 2; fast n; fast) { if (nums[fast] ! nums[slow-2]) { nums[slow] nums[fast]; } } return slow; }性能优化点提前存储n nums.size()避免多次调用前置运算符效率略高于后置10. 刷题方法论建议同类题目集中练习连续刷双指针相关题目26,27,80,283题比较各题解法的异同点解题步骤标准化先厘清题目条件和要求画图模拟简单测试用例再着手编写代码反复练习价值第一遍理解思路第二遍独立实现第三遍优化代码第四遍尝试变种这种分阶段练习法能有效提升算法思维和编码能力。

企业数字化 ERP 产品动态

相关推荐

CEC测试集面试考点全解析：版本差异、函数分类与实验设计

简介：面向进化计算与实参数单目标优化方向的研究者与算法工程师，这份资源汇集了CEC2010、CEC2013、CEC2014、CEC2015、CEC2017五届测试集，可用于新提出算法的基准验证、跨届性能对比，以及向多目标、小生境、约束优化等更复杂问题延… · 2026/11/3 23:15:20

Wireshark数据包导出与在线协作分析实战指南

网络排障这活儿干久了，你会发现一个规律：真正花时间的往往不是“抓包”，而是抓完之后怎么把那一堆数据变成团队能看懂、能复用的东西。Wireshark 的抓包能力大家都不陌生，但数据包导出与在线协作分析这一环，才是把个人… · 2026/11/2 17:11:57

CEC测试集选型与评测避坑指南：从CEC2010到CEC2017

简介：面向进化计算与群体智能方向的研究者及研究生，这份资源汇集了CEC2010、2013、2014、2015、2017五届实参数单目标优化测试集，为算法开发与基准对比提供统一的问题来源。单目标基准是研究多目标优化、小生境与约束优化等更复杂算法的基础&… · 2026/11/3 21:08:22

美妆电商智能推荐系统：协同过滤算法实战

1. 项目背景与核心价值美妆电商平台每天面临海量商品与用户行为的匹配难题。传统人工推荐效率低下，而基于协同过滤的智能推荐系统能有效解决这个问题。我在实际项目中验证过，这套算法能将用户点击率提升35%以上，转化率提升28%左右。这个系统最… · 2026/11/4 4:38:45

Elasticsearch中文分词优化：IK分词器扩展与实战

1. 为什么需要自定义Elasticsearch分词器在搜索引擎和文本处理场景中，分词器的选择直接影响搜索结果的准确性和相关性。Elasticsearch默认提供的标准分词器（Standard Analyzer）对中文支持有限，它只能简单地将中文文本按单个字符切… · 2026/11/4 4:38:45

WPS教育考试版隐藏功能：应用中心与稻壳高效使用指南

不少老师和同学装了WPS教育考试版之后，就把它当成一个“能打字、能排版”的普通Office来用，打开文档、敲完字、保存关闭，一套动作行云流水，然后就没有然后了。我最初也是这么干的，直到有一次帮同事处理一份带复杂公式的… · 2026/11/4 4:38:45

Java 服务中决策模型选型实测：乱码场景下 Jev 与 Laya 准确率与置信度对比

最近在给工单自动分类系统做模型选型，测了一轮候选之后，最后把 Jev 和 Laya 两个决策模型留在台上做了个 PK。先说结论：Jev 在标准中文测试集上 100% 正确，连乱码输入都接近满分命中，而且置信度稳得不像话；… · 2026/11/4 4:38:45

无人机集群路径规划：杜鹃鲶鱼优化算法实战

1. 项目背景与核心价值在无人机集群协同作业场景中，路径规划算法直接决定了任务执行效率与安全性。传统方法常面临三维空间搜索效率低、多约束条件难以平衡、避障实时性不足等痛点。这个项目创新性地将杜鹃鲶鱼优化算法（Cuckoo Catfish Optimization, CC… · 2026/11/4 4:38:45

遗留系统接手难？用Zread从祖传代码生成可维护文档

“祖传代码”这四个字，是从业者对遗留系统最客气的称呼。上周深夜有人发消息给我，说他接手了一个五年前的项目，仓库拉下来，README 六百字，三百字在讲怎么装环境，另外三百字介绍的是一个早就被删掉的模块。他… · 2026/11/4 4:37:45

双极步进电机控制实战：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/4 3:16:49