【每日算法Day 91】数组中单个消失的数字

LeetCode 面试题 17.04. 消失的数字 (opens new window)

题目描述

数组nums包含从0到n的所有整数，但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗？

示例

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

解题思路

常规思路可能是：

1. 对数组进行排序，然后遍历就能找到不存在的数，这种方法的时间复杂度为O(nlogn)。
2. 使用哈希集记录数字是否存在，遍历一遍数组把存在的数字放入集合中，然后再从1~n查找该数字是否存在，这种方法时间复杂度为O(n)，空间复杂度为O(n)。

我们可以使用异或的性质来解决这个问题，输入的数组长度为n，只能存储0~n-1个数，那么我们可以虚拟地把这个数组扩展1位。在长度为n+1的数组中，只有一个数i没有出现过，其他所有的数和其下标都出现1次。那么我们把所有数的下标和出现的数进行异或运算就能得到结果。这种方法时间复杂度为O(n)，空间复杂度为O(1)。

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

另外，还可以用数学知识来解决。1~n的数实际上是等差数列，我们可以用求和公式快速求出其和，然后求出数组中已有元素的和，二者相减得到的就是缺失的数。为避免潜在的整形溢出问题，可以在遍历的每一次循环中相减，再把得到的值加到最终的结果上。

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