​

1. 题目描述

2. 思路分析

方法一：排序+遍历（下一个数不等于上一个数+1，这个下一个数就是消失的数字）。

时间复杂度：O(N*logN） （这里用比较快的qsort排序）

方法二：0+1+2...+(n-1)+n用等差数列求和公式计算，求和结果依次减去数组中的值，最后的结果就是消失的数字。

时间复杂度：O(N)

方法三：单身狗思路，异或。

时间复杂度：O(N)

不了解单身狗问题的小伙伴可以看看这篇文章：https://blog.csdn.net/m0_62531913/article/details/132053191?spm=1001.2014.3001.5501

3.代码实现

因为第一种方法的时间复杂度比较高，这里就不写出来了。

方法二：

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

方法三：

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

​