[数据结构与算法]Leetcode习题：消失的数字（C语言版解法）

在数据结构学习初期，“消失的数字”是我们对于异或运算符较为简单基础的运用。

在这里为了更加透彻理解运用异或运算符，我先对异或运算符的一些性质进行讲解。

一 ·异或运算的真值表

若是认为这个很难记住可以当作是一个无进位的二进制加法

举个例子 1^2 =3? ? ? ? ? ? ? ? ? ? ? 15^15=0

在C语言上异或运算符是针对二进制上0/1的操作

二·异或运算具有交换律和结合律

通过交换律和结合律我们可以得出当一系列数字进行异或运算的时候是无关先后顺序的。

现在让我们来对Leetcode的“消失的数字”进行讲解

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

注意：本题相对书上原题稍作改动

示例 1：

输入：[3,0,1]
输出：2
?

示例 2：

输入：[9,6,4,2,3,5,7,0,1]
输出：8

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/missing-number-lcci

代码实现：

int missingNumber(int* nums, int numsSize)
{
    int a = 0;
    for(int i = 0;i < numsSize;i++)//对缺失数组和不缺失整数的数组进行异或运算
    {
       a = a ^ i ^ *(nums + i);
    }
    return a ^ numsSize;//因为不缺失整数的数组长度是要比输入数组长的，所以在这里我们再次进行一次异或运算
}

现在对上述代码转化成一个数学的实现

这样我用一个数学计算过程来看是不是清晰很多呢？