C/C++用时间复杂度和空间复杂度均为O(N)求一个连续数组中缺失的数字

比如int[a]={0,2,3}则输出1 int[b]={0,1,2,3,5,6}输出4  

代码如下

int main()
{
    int n;
    int* a;
    cout << "输入数组大小：";
    cin >> n;
    a = new int[n];
    for (int i = 0;i < n; i++)
    {
        cin >> a[i];
    }
    int x = 0;
    for (int i = 0; i <= n; i++)
    {
        x ^= i;
    }
    for (int i = 0; i < n; i++)
    {
        x ^= a[i];
    }
    cout << "缺少的数字是：" << x;
    delete a;
}

 利用的原理是两个相同的数异或之后会变成0，我们先让0与0-n的数进行异或，然后在于数组中的值进行异或最终就得到了缺少的那个数，同时时间复杂度和空间复杂的均为O(n)