【05】消失的数字

hellohello~这里是土土数据结构学习笔记🥳🥳

1.消失的数字分析

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

思路1：

先求出数组所有数的和sum1，因为是0~n连续的，只要一个数没有两个，所有我们求出所有两个0 ~n的数的和sum2，再将它们相减即可得到消失的数字🥳🥳

图解如下：

思路2：

利用位操作符来求解，详情点击这里查看：
位与移位操作符详解

按位异或操作符：相同为假，相异为真

而两个相同的数字按位异或得出的结果却是0，因为它们所有位都相同

2.消失的数字完整代码求解

方法一：

int missingNumber(int* nums, int numsSize)
{
int sum = 0;
for(int i = 0; i<numsSize;i++)//数组所有数求和
{
    sum+=*(nums+i);
}
for(int i = 0; i<=numsSize;i++)//假设0~n的数都有两个
{
    sum-=i;//少了一个数的和减去没有少的得到消失的数字的负数
}
return -sum;//返回相反数即可
}

结果如下：

这里的时间复杂度为O(n),符合题意🥳🥳，上面for循环为n，下面也为n，加起来2n，也就是O(n).

方法二：

int missingNumber(int* nums, int numsSize)
{
    int res = 0;
    for (int i = 0; i < numsSize; i++) 
    {
        res ^= nums[i];
    }
    for (int i = 0; i <= numsSize; i++) 
    {
        res ^= i;
    }
        
    return res;
}

同样这里的时间复杂度为O(n),符合题意🥳🥳，上面for循环为n，下面也为n，加起来2n，也就是O(n).

3.结语

✨✨以上就是消失的数字的两种题解啦~ 一种是求和求解，另一种是利用按位异或的特点来求解，两种方法有异曲同工之处，并且时间复杂度都为O(n)，完全符合题意，大家都get到了吗？🥰🥰

以上就是C语言消失的数字所有内容啦~ 大家有什么问题或者更好的方法欢迎写在评论区或私信我哦~ 完结撒花~🥳🥳🎉🎉🎉