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

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

样例

1
2
3

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

输出：3

解题代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty() ) return 0;
        
        int n = nums.size();
        for(int i=0;i<n;++i) {
            
            if(i == nums[i])
                continue;
            while(true) {
                if( nums[i] == i) break;
                int val = nums[i];
                if (val>=0 && val <n) {
                    if(nums[val] != val) {
                        swap(nums[val],nums[i]);
                    }
                }else break;
            }
        }
        int res = n;
        for(int i=0;i<n;++i)
            if(nums[i] != i) 
                res = i;
        //cout << res <<endl;
                //cout << i <<endl;
        return res;
        
        // return 0;
    }
};

二分法优化

抽屉原理：

N 个抽屉，放入 N + 1 个苹果，一定有多一个苹果再任意一个抽屉【也就是说 有一个抽屉有2个苹果】

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int getMissingNumber(vector<int>& nums) {
        if (nums.empty() ) return 0;
       // if(nums.size() == 1) return 1;
        int n = nums.size();
        int l=0,r= n-1;
        while(l<r) {
            int mid = l+r>>1;
            if(nums[mid]  ==  mid) {
                l  = mid+1;
            }else if(nums[mid] > mid) {
                r = mid;
            }else {
                //nums[mid] < mid;
                puts("error");
                //不可能发生
            }
        }
        
        int res = n;
        if(nums[r] != r) res = r;
        //cout << res <<endl;
                //cout << i <<endl;
        return res;
        
        // return 0;
    }
};