[数据结构与算法]面试题 17.04. 消失的数字（四种思路：C实现）

题目

面试题 17.04. 消失的数字

实现思路

思路1

排序的方式：

1. 使用C语言库函数qsort()排序，这样数字就和数组下标相对应；
2. 然后遍历数组nums,用nums[ i+1 ] - nums[ i ] 判断，等于1表示两个数相邻，等于2表示缺失了的那个数；
3. 把对应的下标 i+1 输出即可；

注意：用于C语言的库qsort函数时间复杂度是O(nlogn)，与题目不符合，所以这里就是提供思路，不提供实现代码；

思路2及其代码实现

哈希表的方式：

1. 开辟一个数组初始值赋为-1，然后对应下标保存对应数字；
2. 然后再遍历数组，发现为-1的值的下标就为消失数字；

int missingNumber(int* nums, int numsSize){

    //开辟numsSize+1大小的数组
    int* newNums = (int*)malloc(sizeof(int)*(numsSize+1));
	//给数组赋值 -1
    for(int i = 0;i < numsSize+1;i++){
        newNums[i] = -1;
    }
	//给newNums数组赋nums的数字，把下标和数字对应映射起来
    for(int i  = 0;i <numsSize;i++)
    {
        newNums[nums[i]] = nums[i];
    }
    //找消失的数字
    int i = 0;
    for(i= 0;i <numsSize+1;i++){
        if(newNums[i] == -1)
            break;
    }
    return i;    
}

思路3及其代码实现

相邻差值相减：

1. 直接先求0到n的累加和sum,然后遍历数组求和sumNums;
2. 用 sum - sumNums = 消失的数字。

int missingNumber(int* nums, int numsSize){
    //先求 0 - n 的所有和
    //等差数列求和
    int sum = ( (0 + numsSize)* (numsSize+1)) >>1;
    int sumNums = 0; //保存nums数组的和
    //求数组的和
    for(int i = 0;i<numsSize;i++){
        sumNums += nums[i];
    }
    //差值为消失的数字
    return sum - sumNums;
}

思路4及其代码实现

异或性质：

1. 0^x = x;
2. x^x = 0; 同样的数异或两次得到零
3. 异或满足交换律

异或实现思路：
4. 先异或[0,n]的所有数字，再异或nums数字的所有数字：
5. 由于想同的数异或会得到0,并且0异或任意数结果都是任意数，
6. 所以再本题中，异或两次的会被变为0，异或一次的就不会发生变化：那么小时的数字就会出来了 比如 输入：[3,0,1] ：先异或：0到n的所有数字：X^ 1 ^ 2^3；再异或数组： X^ 1 ^ 2^ 3 ^ 3^ 0 ^ 1 = 0^ 1^ 1^ 2 ^3 ^3 = 2; 即2是消失的数字。

int missingNumber(int* nums, int numsSize){
        //先异或0-numsSize的所有数字
        int x = 0;
        for(int i = 0 ;i<=numsSize;i++){
                x ^= i;
        }
        //再异或nums数组所有的值
        for(int i = 0;i <numsSize;i++){
            x ^= nums[i];
        }
        //最后的结果就是消失的数字
        return x;
}