每日一题：消失的数字
数字 每日 消失
2023-06-13 09:18:27 时间
链接: 消失的数字
思路
使用排序
因为题目说这个数组是从0到n的所有整数，所以首先大家想到的可能是将这个数组进行排序比如冒泡排序。 这个想法虽然不错，但是题目又要求是否可以在O(n) 时间复杂度完成，所以这里不推荐使用排序的方法。
利用求和
由于这个数组的一个特点：它是从0到n的所有整数组成的，只是缺了一个。 那就有了一个想法，就是先把0到n完整的相加在一起，减掉这个数组的和，就等于这个缺的这个数字了！，简单的说就是这样子：
0到n等差数列的和 - 数组所有数的和 = 消失的数字
int missingNumber(int* nums, int numsSize){
//等差数列的和
int all = ((0 + numsSize) * (numsSize + 1)) / 2;
//数组元素的和
int sum = 0;
for(int i = 0; i < numsSize; i++)
{
sum += nums[i];
}
return all - sum;
}利用异或
首先要知道异或有一个特点，就是你拿一个数字去异或一个数字后，再拿这个异或完的数字去异或原来的其中一个数字，结果就是另一个一起异或的数字。 基于这个特点，我们有了这个思路：
用0去异或数组中的每一个数，然后再去异或0到n的每一个数字，最后结果就是消失的数字。
int missingNumber(int* nums, int numsSize){
int n=0;
for(int i=0;i<numsSize;i++)
n^=nums[i];
for(int i=0;i<=numsSize;i++)//这里是n+1个数字，记得加上等于号
n^=i;
return n;
}学到知识的朋友不要吝啬你们的赞哦(⊙o⊙)！