题解 | #缺失数字#

算法思想一：二分查找

解题思路：

利用二分查找法找出缺失数字

算法解析：
1、初始化：左边界 $i = 0$ ，右边界 $j = len(a) - 1$ ；代表闭区间 $[i, j]$ 。
2、循环二分：当 $i≤j$ 时循环（即当闭区间 $[i, j]$ 为空时跳出）；
1、计算中点 $m = (i + j) // 2$ ，其中 "//" 为向下取整除法；
2、若 $a[m] = m$ ，则 “右子数组的首位元素” 一定在闭区间 $[m + 1, j]$ 中，因此执行 $i = m + 1$ ；
3、若 $a[m]=m$ ，则 “左子数组的末位元素” 一定在闭区间 $[i, m - 1]$ 中，因此执行 $j = m - 1$ ；
3、返回值：跳出时，变量 $i$ 和 $j$ 分别指向 “右子数组的首位元素” 和 “左子数组的末位元素” 。因此返回 $i$ 即可。

图解：

代码展示：

Python版本

class Solution:
    def solve(self , a ):
        # write code here
        # 初始化双指针
        i, j = 0, len(a) - 1
        while i <= j:
            # 确定二分中点
            m = (i + j) // 2
            # 如果 a[m] == m，则未知的数字在 【m+1, j】
            if a[m] == m: i = m + 1
            # 否则未知的数字在 【i, m-1】
            else: j = m - 1
        return i

复杂度分析

时间复杂度 $O(logn)$ ： $n$ 表示数组的长度，二分查找时间复杂度

空间复杂的 $O(1)$ ：仅使用常数级变量空间

算法思想二：位运算

解题思路：

已知0和1异或的时候相同的异或结果为0，不同的异或结果为1，根据上面的规律我们得到

$a^a=0$ ；自己和自己异或等于0
$a^0=a$ ；任何数字和0异或还等于他自己
$a ⊕ b ⊕ c=a ⊕ c ⊕ b$ ；其中 $⊕$ 为异或运算，则异或运算具有交换律

有了这3个规律，只需要把所有的数字都异或一遍，最终的结果就是我们要求的那个数字

代码展示：

JAVA版本

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 找缺失数字
     * @param a int整型一维数组 给定的数字串
     * @return int整型
     */
    public int solve (int[] a) {
        // write code here
        // 初始化
        int xor = 0;
        // 循环遍历数组 对数据依次进行异或计算
        for (int i = 0; i < a.length; i++)
            xor ^= a[i] ^ (i + 1);
        return xor;
    }
}

复杂度分析

时间复杂度O(n)：n表示数组的长度，遍历数组时间

空间复杂的O(1)：仅使用常数级变量空间

算法思想三：数学法

解题思路：

利用等差数列前 $n$ 项和来解题（差值为1）

如果不缺那个数字的话，这个数组的所有数字可以组成一个等差数列，只需要根据公式（ $s_n = (a_1+a_n)*n / 2$ ）求和，然后再减去数组中所有的数字即可

代码展示：

Python版本

class Solution:
    def solve(self , a ):
        # write code here
        # 0-n的数据长度
        length = len(a) + 1
        # 使用数学法，根据前n项和计算
        return (length - 1) * length // 2 - sum(a)

复杂度分析

时间复杂度 $O(n)$ ： $n$ 表示数组的长度，sum求和时间

空间复杂的O(1)：仅使用常数级变量空间