C语言每日一题（16） 消失的数字

题目链接

一.题目描述

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

二.题目分析

方法1 异或法

基于异或的思想，将0与数组中的数一一进行异或后得到的值，再与0~异或，完后会发现得到的值就是剩下来的消失的值（不理解可以看看我的文章《找单身狗1，2》）。

步骤（力扣环境下）

1.定义一个开始异或的值为0。

2.循环数组并将数组的值一一异或，将得到后的值再与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^=i;
    }
    return n;
 
}

方法2 等差数列求和法

测试用例给的都是公差为1的等差数列，然后在里面找缺失的值，可以先求出这个等差数列的总和，再减去数组里的值，这样剩下的值就是消失的值。

步骤

1.定义一个N来保存数组的元素个数。

2.利用等差数列求和公式（首项加尾项的和乘以项数除以2）得到总和

3.再循环整个数组，减去数组里的值，返回剩下的值。

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