268 缺失数字

题目：
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。

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

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

方法一：排序法

思路： 先将数组排序，然后判断排序后的数组数字是否挨着，即若两个相邻数字之间相差2，则这两个数字间的那个数字即为缺失数字

代码：

public int missingNumber(int[] nums) {
    Arrays.sort(nums);
    // 判断 n 是否出现在末位
    if (nums[nums.length-1] != nums.length) {
        return nums.length;
    }
    // 判断 0 是否出现在首位
    else if (nums[0] != 0) {
        return 0;
    }
    // 此时缺失的数字一定在 (0, n) 中
    for (int i = 1; i < nums.length; i++) {
        int expectedNum = nums[i-1] + 1;
        if (nums[i] != expectedNum) {
            return expectedNum;
        }
    }
    // 未缺失任何数字（保证函数有返回值）
    return -1;
}

复杂度：
时间复杂度：O(nlogn),排序的复杂度
空间复杂度：O(1),实际上跟采用的排序算法有关

方法二：哈希法

思路：
先将nums数组中所有数放进哈希表，然后寻找从0到n的哪一个数不在哈希表中，返回这个数字

代码：

public int missingNumber(int[] nums) {
    //新建一个HashSet,将nums中所有元素加入HashSet
    Set<Integer> set = new HashSet<>();
    for(int num: nums)
        set.add(num);
    //判断从0到nums.length范围内数是否在set中，如果有数不在，返回这个数
    for(int i = 0; i <= nums.length;i++)
        if(!set.contains(i))
            return i;
    return -1;
}

时间复杂度：O(n)。HashSet的插入和查询操作都是O(1),对每一个数都进行这个操作，总时间复杂度为O(n)
空间复杂度：O(n)。需要HashSet存储这些数

方法三：数学方法

思路：
用高斯求和公式求出从1到n的和，即：

\sum^{n}_{i = 0}\frac{n(n-1)}{2}

然后再将nums中的元素求和，二者相减即为缺失的元素

代码：

public int missingNumber(int[] nums) {
    int expectedSum = nums.length*(nums.length + 1)/2;
    int sum = 0;
    for (int num : nums) 
        sum += num;
    return expectedSum - sum;
}

时间复杂度：
高斯求和的复杂度为O(1),数组元素求和的复杂度为O(n)。总时间复杂度为O(n)
空间复杂度: O(1)

方法四：位运算

思路：
如果数组中没有丢失数字的话，比如[0,1,2]。其中每个数字0，1，2作为数组索引中出现一次，作为值中又出现一次，总共出现两次

一旦丢失了数字，比如[0,1,3]。0，1这两个数字出现两次（作为索引一次，作为值一次），而3这个数字只作为值出现一次。

而我们知道，一个数字自己异或自己得到的结果为0。因此如果我们异或数组nums的所有索引和所有值。最终0，1会自己异或自己进而为0。最终异或结果其实是3和2的异或值。其中，3为数组nums的长度，2为缺失的数字

而数组nums的长度我们是知道的，上述得到的结果再异或一下它，得到的2即为丢失的数字

代码：

public int missingNumber(int[] nums) {
    int res = 0;
    for(int i = 0; i < nums.length; i++)
        res = res ^ i ^ nums[i];
    return res ^ nums.length;
}

• 时间复杂度:O(N)
• 时间复杂度:O(1)