Vanishing numbers

Array nums Contains from 0 To n All integers of , But one of them is missing . Please write code to find the missing integer .

The required time complexity is O(n), The space complexity is O(1).

Example 1：

 Input ：[3,0,1]
 Output ：2

Example 2:

 Input ：[9,6,4,2,3,5,7,0,1]
 Output ：8

  Train of thought ：

Using the properties of XOR ,res = res ^ x ^ x. XOR the same value twice , Then the result is equal to itself , So we are right res from 0-nums.length To engage in exclusive or , At the same time nums XOR the values in the array , If there is a repetition, it will disappear , So finally res The value of is a number that appears only once , That is to say nums The missing number in the array .

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

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

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

Train of thought two ：

Before finding out n+1 Sum of numbers , Subtract the number in the array , It's the disappearing number .

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

Train of thought three ：

Open up another large space array , The number of the original array is used as the index of the new array , Then mark it as 1, Then traverse the new array instead of 1 The index of is what you want .

int missingNumber(int* nums, int numsSize){
    int i;
   int* tmp=(int* )malloc(sizeof(int)*(numsSize+1));
   for(i=0;i<numsSize;i++){
       tmp[nums[i]]=1;
   }
   for(i=0;i<numsSize;i++){
       if(tmp[i]!=1)
       break;
   }
   return i;
}

Train of thought four ：

Hashtable

int missingNumber(int* nums, int numsSize){
    int f[10000]={0};
    int i;
    for(i=0;i<numsSize;i++){
        f[nums[i]]++;
    }
    for(i=0;i<10000;i++){
        if(f[i]==0)
        break;
    }
    return i;
}

Is there any good way , Leave a message in the comment area and we will discuss .