剑指offer50_0到n-1中缺失的数字

0到n-1中缺失的数字

---

一个长度为 n−1 的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围 0 到 n−1 之内。

在范围 0 到 n−1 的 n 个数字中有且只有一个数字不在该数组中，请找出这个数字。

数据范围

1≤n≤1000

样例

输入：[0,1,2,4]输出：3

---

算法思路（二分查找）

1. 核心思想：
   • 利用有序数组的特性，通过二分查找定位缺失的数字。
   • 关键观察：在无缺失的数组中，数值 nums[i] 应等于索引 i；若 nums[mid] > mid，说明缺失数字在左半部分。
2. 关键步骤：
   • 初始化：左指针 l = 0，右指针 r = nums.size()（注意右边界开区间）。
   • 二分查找：
     • 若 nums[mid] > mid，缺失数字在左半部分（r = mid）。
     • 否则，缺失数字在右半部分（l = mid + 1）。
   • 终止条件：l == r 时，r 即为缺失的数字。

维度	说明	公式
时间复杂度	二分查找每次将搜索范围减半。	$O(\log n)$
空间复杂度	仅使用常数空间（指针变量）。	$O(1)$

---

class Solution {
public:int getMissingNumber(vector<int>& nums) {if (nums.empty()) return 0;  // 处理空数组特例int l = 0, r = nums.size();  // 初始化左右指针（右开区间）while (l < r) {              // 二分终止条件int mid = l + r >> 1;    // 等价于 (l + r) / 2if (nums[mid] > mid) r = mid;  // 缺失在左半部分else l = mid + 1;        // 缺失在右半部分}return r;                   // 返回缺失数字}
};

示例演示

输入：nums = [0, 1, 2, 4, 5]（缺失 3）
二分过程：

1. 初始范围 [0, 5)：
   • mid = 2，nums[2] = 2 → 右移 l = 3。
2. 范围 [3, 5)：
   • mid = 4，nums[4] = 5 > 4 → 左移 r = 4。
3. 范围 [3, 4)：
   • mid = 3，nums[3] = 4 > 3 → 左移 r = 3。
4. 终止：l = r = 3，返回 3。

边界情况处理

输入	输出	说明
[]	0	空数组时缺失 0
[0]	1	缺失 1
[0, 1, 2, 3]	4	缺失 4（末尾缺失）
[1, 2, 3]	0	缺失 0（开头缺失）

---

扩展

1. 异或解法：

   • 利用 a ^ a = 0 的性质，遍历数组和完整序列 0~n 进行异或，最终结果为缺失数字。
   • 时间复杂度：$O(n)$，空间复杂度：$O(1)$。

   int res = nums.size();  // 初始化为n（因为循环中少一个数）
   for (int i = 0; i < nums.size(); i++) {res ^= i ^ nums[i];
   }
   return res;
   

2. 数学求和法：

   • 计算 0~n 的和 S = n(n+1)/2，减去数组总和，差值即为缺失数字。
   • 注意可能的整数溢出问题。