1. 问题背景与核心挑战这道算法题看似简单却暗藏多个考察点。给定一个长度为n的数组其中元素取值范围为[1,n]要求找出[1,n]范围内所有未出现在数组中的数字。举个具体例子对于输入[4,3,2,7,8,2,3,1]输出应该是[5,6]因为数字5和6没有出现在数组中。这类问题的典型特征是数组长度与元素取值范围存在明确关联这种特殊结构往往提示我们可以利用数组本身作为标记空间。在实际工程场景中类似问题常见于数据校验、完整性检查等场景比如检测连续ID序列中缺失的ID号。2. 常规解法与性能分析2.1 哈希表法直观解法最直观的解法是使用哈希集合def findDisappearedNumbers(nums): num_set set(nums) return [i for i in range(1, len(nums)1) if i not in num_set]这种方法时间复杂度O(n)空间复杂度O(n)。虽然能解决问题但面试官通常会期待更优的空间复杂度解法。2.2 排序遍历法先排序再顺序检查def findDisappearedNumbers(nums): nums.sort() res [] expected 1 for num in nums: while expected num: res.append(expected) expected 1 if expected num: expected 1 # 处理末尾缺失情况 res.extend(range(expected, len(nums)1)) return res时间复杂度O(nlogn)空间复杂度O(1)不考虑输出空间。虽然空间优化了但时间效率反而下降。3. 最优解法原地标记法3.1 核心思路利用数组元素值本身作为索引标记遍历数组将nums[abs(num)-1]对应的值标记为负数再次遍历仍为正数的位置索引1就是缺失的数字3.2 完整实现def findDisappearedNumbers(nums): for num in nums: index abs(num) - 1 if nums[index] 0: nums[index] * -1 return [i1 for i in range(len(nums)) if nums[i] 0]3.3 复杂度分析时间复杂度O(n)两次线性遍历空间复杂度O(1)原地修改仅使用常量额外空间4. 关键细节与边界处理4.1 元素去重处理当数组存在重复元素时同一个位置可能被多次标记。由于我们使用绝对值判断重复标记不会影响最终结果。4.2 索引越界防护元素值范围保证在[1,n]所以abs(num)-1始终是有效索引无需额外检查。4.3 恢复原始数组可选如果需要保持输入数组不变可以在最后恢复被修改的值for i in range(len(nums)): nums[i] abs(nums[i])5. 变种问题与扩展思考5.1 找出重复的数字类似思路可以解决LeetCode 287寻找重复数def findDuplicate(nums): for num in nums: idx abs(num) if nums[idx] 0: return idx nums[idx] -nums[idx]5.2 缺失多个数字的通用解法当元素范围与数组长度不一致时如范围[1,m]需要结合数学求和公式def findMissingNumbers(nums, m): full_sum m*(m1)//2 actual_sum sum(set(nums)) # 去重 missing_sum full_sum - actual_sum # 进一步分解missing_sum为两个缺失数字的组合6. 工程实践中的注意事项大数据量处理当数组规模极大时原地修改法能显著减少内存占用并行化可能标记阶段可以分块并行处理但需要注意写冲突流式处理适配如果数据是流式输入需要改用位图等压缩数据结构关键技巧在内存受限环境下可以考虑分块处理。将范围分成k个区间每次只处理一个区间的标记通过多次遍历降低内存需求。7. 测试用例设计建议完整测试应包含以下场景test_cases [ ([1,1], [2]), # 最小长度重复元素 ([4,3,2,7,8,2,3,1], [5,6]), # 标准案例 ([1,2,3,4], []), # 无缺失 ([2,2,2,2], [1,3,4]), # 极端重复 ([1], []), # 单元素无缺失 ([2,2], [1]) # 单元素缺失 ]8. 不同语言实现差异8.1 Java版本注意事项public ListInteger findDisappearedNumbers(int[] nums) { for (int num : nums) { int idx Math.abs(num) - 1; if (nums[idx] 0) { nums[idx] * -1; } } ListInteger res new ArrayList(); for (int i 0; i nums.length; i) { if (nums[i] 0) { res.add(i 1); } } return res; }注意Java数组没有Python的列表推导式需要显式创建结果列表。8.2 C版本优化vectorint findDisappearedNumbers(vectorint nums) { for (auto num : nums) { int idx abs(num) - 1; nums[idx] -abs(nums[idx]); } vectorint res; for (int i 0; i nums.size(); i) { if (nums[i] 0) { res.push_back(i1); } } return res; }C版本需要注意负数转换时的溢出问题使用abs双重保险。9. 算法可视化理解以输入[4,3,2,7,8,2,3,1]为例第一次遍历标记过程处理4标记位置37→-7处理3标记位置22→-2处理2标记位置13→-3处理7标记位置63→-3处理8标记位置71→-1处理2位置1已是负数-3保持不变处理3位置2已是负数-2保持不变处理1标记位置04→-4最终数组状态[-4,-3,-2,-7,8,2,-3,-1]正数位置索引4(值8)、5(值2) → 缺失数字5,610. 实际应用场景延伸数据库记录校验检查连续主键ID是否存在缺失日志分析检测按时间顺序的事件流是否完整质量监控验证设备上报的序列号是否连续库存管理盘点商品编号是否存在断号在分布式系统中类似的算法变种可用于检测数据分片是否完整。我曾在一个日志分析系统中使用类似方法成功发现了数据采集链路中某个节点的丢包问题。