Daily question 1: missing numbers

link : Missing numbers

Usage sort

Because the title says that this array is from 0 To n All integers of , So the first thing you think of may be sorting this array, such as bubble sorting .
Although the idea is good , But the question asks whether it can be done in O(n) Time complexity complete , So here Sorting is not recommended .

Using summation

Because of a feature of this array ： It's from 0 To n All integers of , Only one is missing .
Then I have an idea , It's about putting 0 To n Add them all together , Subtract the sum of this array , It is equal to the missing number ！, Simply put, it's like this ：

0 To n The sum of an arithmetic sequence - The sum of all numbers in the array = Missing numbers

int missingNumber(int* nums, int numsSize){
    
    // The sum of an arithmetic sequence 
    int all = ((0 + numsSize) * (numsSize + 1)) / 2;

    // The sum of array elements 
    int sum = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        sum += nums[i];
    }

    return all - sum;
}

Using XOR

First of all, we should know that XOR has a characteristic , You take a number to XOR a number , Take the XOR number to XOR one of the original numbers , The result is another XOR number .
Based on this feature , We have this idea ：

use 0 Remove every number in the XOR array , And then XOR 0 To n Every number , The final result is the number of disappearances .

int missingNumber(int* nums, int numsSize){
    
    int n=0;
    for(int i=0;i<numsSize;i++)
        n^=nums[i];
    for(int i=0;i<=numsSize;i++)// Here is n+1 A digital , Remember to add the equals sign 
        n^=i;
    return n;
}

Learn knowledge of the friends do not mean your praise (⊙o⊙)！