题目
缺失的数字
信息
- 类型：问答
- 难度：⭐⭐
考点
位运算,异或操作,数组处理
快速回答
给定一个包含 n 个不同数字的数组，这些数字取自 0, 1, 2, ..., n，请找出数组中缺失的那个数字。
核心解法：
- 利用异或运算的自反性（X⊕X=0）和恒等性（X⊕0=X）
- 将数组所有元素与完整序列
0 到 n进行异或 - 最终结果即为缺失数字
时间复杂度：O(n)，空间复杂度：O(1)
解析
原理说明
异或运算（⊕）有三个关键特性：
- 自反性：X ⊕ X = 0
- 恒等性：X ⊕ 0 = X
- 交换律和结合律：运算顺序不影响结果
假设完整序列为 0,1,2,...,n（共 n+1 个数），数组包含其中 n 个数。将所有数组元素与完整序列异或：
- 存在的数字出现两次 → 异或结果为 0
- 缺失的数字出现一次 → 异或结果保留该值
代码示例
def missing_number(nums):
missing = len(nums) # 初始化为 n（完整序列的最大值）
for i, num in enumerate(nums):
missing ^= i # 异或当前索引（0 到 n-1）
missing ^= num # 异或数组元素
return missing
# 测试用例
print(missing_number([3,0,1])) # 输出 2
print(missing_number([9,6,4,2,3,5,7,0,1])) # 输出 8最佳实践
- 初始化技巧：直接用
n（数组长度）初始化结果，避免单独处理最大值 - 单次遍历：在枚举数组时同步处理索引和元素
- 防溢出：相比求和法（sum(0..n) - sum(nums)），位运算无整数溢出风险
常见错误
- 边界处理错误：忘记处理最大值
n（完整序列包含 n 但数组不包含） - 索引范围混淆：枚举索引应从 0 开始到 n-1（Python 的
enumerate自动处理） - 错误初始化：若初始化为 0 需额外异或
n（见备选方案）
备选方案对比
| 方法 | 时间复杂度 | 空间复杂度 | 缺点 |
|---|---|---|---|
| 位运算（异或） | O(n) | O(1) | 逻辑较抽象 |
| 数学求和 | O(n) | O(1) | 可能整数溢出 |
| 哈希表 | O(n) | O(n) | 额外空间开销 |
| 排序后遍历 | O(n log n) | O(1) | 效率较低 |
扩展知识
- 异或的进阶应用：
- 找出现奇数次的数字（其他数字出现偶数次）
- 不使用临时变量交换两个整数：
a ^= b; b ^= a; a ^= b
- 变种问题：
- 缺失两个数字：结合分治思想和异或特性
- 有序数组中的缺失数字：可用二分查找优化到 O(log n)
