剑指 Offer 53

思路

方法一：顺序查找

顺序查找第一个nums[i]不等于下标 i 的数，这时的下标 i 就是缺少的数。

复杂度分析

时间复杂度：O(n)

空间复杂度：O(1)

方法二：二分法

复杂度分析

时间复杂度：O(logn)

空间复杂度：O(1)

 1 class Solution {
 2 public:
 3     int missingNumber(vector<int>& nums) {
 4         int left, right, mid;
 5         left = 0;
 6         right = nums.size()-1;
 7 
 8         while(left <= right) {
 9             mid = (left + right) / 2;
10             if(nums[mid] <= mid) {
11                 left = mid + 1;
12             } else if(nums[mid] > mid) {
13                 right = mid - 1;
14             } 
15         }
16 
17         return left;
18     }
19 };

参考

面试题53 - II. 0～n-1 中缺失的数字（二分法，清晰图解）

相似题目：

剑指 Offer 53 - I. 在排序数组中查找数字 I