剑指 Offer 53 - II. 0～n-1中缺失的数字

原题链接

难度：$easy$

---

题目描述

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

示例 1:

输入: [0,1,3]
输出: 2

示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

限制：

$1<=数组长度<=10000$

---

算法1

(二分)

• 排序数组中的搜索问题，首先想到 二分法 解决，排序数组使用双指针也是高频选项~
• 根据题意，数组可以按照以下规则划分为两部分。
  • 左子数组 nums[mid] == mid
  • 右子数组 nums[mid != mid
• 缺失的数字等于 “右子数组的首位元素” 对应的索引；
  
  

复杂度分析

• 时间复杂度：$O(logn)$。

• 空间复杂度 : $O(1)$

C++ 代码

class Solution {
public:int missingNumber(vector<int>& nums) {// 特判 特殊情况if (nums.empty()) return 0;int n = nums.size() + 1;if (nums.back() == n - 2) return n - 1;int l = 0, r = n - 2;while (l < r) {int mid = (l + r) / 2;if (nums[mid] != mid) r = mid;else l = mid + 1;}return l;}
};

---

算法2

(哈希)

首先遍历数组 nums，将数组中的每个元素加入哈希集合，然后依次检查从 0 到 n−1 的每个整数是否在哈希集合中，不在哈希集合中的数字即为缺失的数字。

复杂度分析

• 时间复杂度：$O(n)$。

• 空间复杂度 : $O(n)$

C++ 代码

class Solution {
public:int missingNumber(vector<int>& nums) {unordered_set<int> hash;int n = nums.size() + 1;for (int i = 0; i < nums.size(); i ++) {hash.insert(nums[i]);}int missing = -1;for (int i = 0; i <= n - 1; i ++) {if (!hash.count(i)) {missing = i;break;}}return missing;}
};