【05】消失的数字

news/2024/7/27 8:03:41/文章来源:https://blog.csdn.net/Renswc/article/details/136694699

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

💥个人主页：大耳朵土土垚的博客
💥所属专栏：C语言函数实现
感谢大家的观看与支持🌹🌹🌹
有问题可以写在评论区或者私信我哦~

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;
}