每日一题之灵活运用C语言#面试题#消失的数字

请编写代码找出那个缺失的整数。

你有办法在O(n)时间内完成吗？

示例 1：

输入：[3,0,1]
输出：2

示例 2：

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

如果没有O（n）这一限制条件，相信很多小伙伴都能迅速作答，但一加上时间复杂度难度就加大了一截。

要解决这道题，首先我们要明白什么O（n）时间内。

这是一个时间复杂度的限制条件，即代码运行时长与输入的值大致呈现一个线性关系。

        我们知道，固定几个数的位异或结果为一个固定值，这个值与数字异或的顺序无关即：a^b^c = a^c^b = b^a^c = b^c^a = c^a^b = c^b^a. 且 两数相同的异或结果为0 即 a^a = 0；由此我们可以想到 a^b^c = x,   x^b^c = a。

由此第一种解法也就出来了。

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; ++i)
    {
        x ^= i;
    }
    return x;
}

两个for循环可以互换顺序，第二个for循环是为了求出0~N中所有数的异或结果，第一个for循环是是为了抵消和第一个for循环重复的数，剩下的结果是什么，缺失的数就是什么。

当然也可以将两个for循环融合为一个for循环，但这样做会大大降低代码的可读性并且对于时间运算并没有优化。

        我们知道所有数的范围是0~N，那么利用等差求和公式 Sn = n*[a（n）+a（1）] / 2, 求得和再挨个减去输入的值，差值便是消失的数。

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

        这一类题首先想到将这个所求范围内的所有数利用求和或者异或的方式结合在一起然后再利用循环一个个去消掉无序数组中存在的数。

（如果有更多更好的方法请私小编）