题解 | #缺失数字#

方法一：求和
核心思想：由题意可知，给定数组为0 - n中的n + 1个数去除一个数所得，所以只要将0 - n中所有数的和与给定数组的和做差，所得结果即为缺少的数。
既假设给定数组为$[0, 1, ..., k - 1, k + 1, ..., n],$ 缺少数字为k。
此时设数组和为:

0到n求和所得结果为：

显然有： ，即为所求的缺失数字。
实现中sum可利用求和公式求得。
核心代码：

class Solution {
public:
    int solve(vector<int>& a) {
        int n = a.size(), num = 0;
        int sum = n * (n + 1) / 2; //由求和公式得到sum
        for(int i = 0; i < n; ++i) { 
            num += a[i]; 
        } 
        return sum - num;
    }
};

复杂度分析：
时间复杂度：$O（n)$，求数组和时需要遍历数组一次
空间复杂度：$O（1）$，只用到了常数空间

方法二：位运算
核心思想：位运算的方法基于几个公式：

既同一个数与自身异或结果为0， 任何数与0异或结果为自身, 异或运算满***换律
为求得题中缺失数字，可以令数组中全部数字异或，再与0 - n 中所有数字异或。
既数组异或结果:

0 - n 异或结果:

上述两者异或结果

class Solution {
public:
    int solve(vector<int>& a) {
        int n = a.size();
        int sum = 0, num = 0;
        for(int i = 0; i < n; ++i) { 
            sum ^= (i + 1); //求得sum = 0 ^ 1 ^ ... ^ n
            num ^= a[i]; //求得num = 0 ^ 1 ^ ... ^ (k - 1) ^ (k + 1) ^ ... ^ n 
        } 
        return (sum ^ num);
    }
};

复杂度分析：
时间复杂度：$O（n)$，需要遍历数组进行异或
空间复杂度：$O（1）$，只用到了常数空间

方法三：二分查找
核心思想：由题可知数组是有序排列，可以通过二分查找得到缺失数字
因为缺失了一个数字，所以在缺失的数字之前，有a[i] = i,
在缺失的数字之后，有a[i] > i,

class Solution {
public:
    int solve(vector<int>& a) {
        int i = 0, j = a.size() - 1;
        while(i <= j) { 
            int mid = (i + j) / 2; 
            if(a[mid] == mid) { 
                i = mid + 1; //此时答案位于mid右侧 
            } else{ 
                j = mid - 1; 
            } 
        } 
        return i; 
    }
};

复杂度分析：
时间复杂度：$O（log n)$，即为二分查找复杂度
空间复杂度：$O（1）$，只用到了常数空间