【LeetCode】消失的数字

面试题 17.04. 消失的数字

题目描述：

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

//题目框架
int missingNumber(int* nums, int numsSize){
}

解法一：

因为nums数组中包含的是0到n的整数，其中缺了一个，所以一共是n个整数了。
所以可以开辟一个numSize+1大小的临时数组tmp(numsSize=n)，这个数组的下标也就是从0到n，
此时可以遍历nums数组中的数据nums[i]，并将tmp数组nums[i]位置上的数据置为nums[i]。
最后通过检查tmp数组那个位置上的数据没有被重置，返回该位置的下标即可。
参考代码如下：

//时间复杂度：O(n)
//空间复杂度：O(n)
int missingNumber(int* nums, int numsSize)
{
    int* tmp = (int*)malloc((numsSize+1) * sizeof(int));
    
    //用 -1 初始化临时数组
    for(int i = 0; i < numsSize + 1; ++i)
    {
        tmp[i] = -1;
    }
    
	//将tmp数组中的数据进行相应的重置
    for(int i = 0;i < numsSize; ++i)
    {
        tmp[nums[i]] = nums[i];
    }

	//遍历查找没有被重置的位置，并返回
    for(int i = 0; i < numsSize + 1; ++i)
    {
        if(-1 == tmp[i])
        {
            free(tmp);
            return i;
        }
    }
    
    return -1;
}

解法二：

可以通过异或的方式来解决这道题。
异或运算符^作为位运算符，对于位上相同的情况异或结果为0，位上不同的情况异或结果为1。
这里要知道两点：
0和任何数异或结果是它本身；
一个数和自身异或结果是0。

0^n=n;
n^n=0;

根据异或的特性，可以先将nums数组中的数据都异或一遍，然后将异或的结果再从0到n异或一遍。这样，根据相同的数据异或结果是0，最终留下的就是所谓消失的数字了。
参考代码如下：

//时间复杂度：O(n)
int missingNumber(int* nums, int numsSize)
{
    int x = 0;
    for(int i = 0; i < numsSize; ++i)
    {
        x ^= nums[i];
    }
    for(int i = 0; i < numsSize + 1; ++i)
    {
        x ^= i;
    }
    return x;
}

解法三：

可以通过数学的方式来解决这道题。
因为0到n的数是一个等差数列，根据等差数列求和公式求出0到n的总和，然后和nums数组中的数据进行差值运算，就能找出最终消失的数字了。
参考代码如下：

int missingNumber(int* nums, int numsSize)
{
    int sum = 0;
    for(int i = 0; i < numsSize; ++i)
    {
        sum += nums[i];
    }
    return ((0+numsSize) * (numsSize+1)) / 2 - sum;
}