廖家龙的博客网站
剑指Offer_53-2_0～n-1中缺失的数字
廖家龙 用心听，不照做
  2019-06-30 20:58:00   2024-07-19 11:19:03    229 字  1 分钟

题目描述：

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

示例：

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

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

限制：1 <= 数组长度 <= 10000

解法1：

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int missingNumber(vector<int>& nums) {

        for (int i = 0;i < nums.size();++i) {

            if (nums[i] != i) return i;
        }

        return nums.size();
    }
};

解法2：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int missingNumber(vector<int>& nums) {

        if (nums.empty()) return NULL;

        int l = 0, r = nums.size() - 1;

        while (l <= r) {

            int mid = (l + r) / 2;

            if (nums[mid] != mid) r = mid - 1;
            else l = mid + 1;
        }

        //输入：[1,2] 输出：0
        //输入：[0,1,2] 输出：3
        if (r == -1 || nums[r] == r) ++r;  

        return r;
    }
};
  1. 1. 题目描述：
    1. 1.1. 解法1：
    2. 1.2. 解法2：二分查找
  1. 1. 题目描述：
    1. 1.1. 解法1：
    2. 1.2. 解法2：二分查找