面试题 17.04. 消失的数字（四种思路：C实现）

面试题 17.04. 消失的数字

排序的方式：

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

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

哈希表的方式：

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  
 
思路3及其代码实现 
相邻差值相减：
 
直接先求0到n的累加和sum,然后遍历数组求和sumNums;
用 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 
 
思路4及其代码实现 
异或性质：
 
0^x = x;
x^x = 0; 同样的数异或两次得到零
异或满足交换律
 
 
异或实现思路：
 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