Daily question 1: the number of numbers in the array

link : The number of occurrences of numbers in an array

---

The question is “ Missing numbers ” An advanced version of , Readers who haven't touched can read this first ：

link ： Missing numbers

---

Ideas ： We still use XOR , Only this problem needs to find two numbers , So we have to find the XOR of these two numbers first ：

First, the array nums The numbers in are XOR again , The result is the XOR number of the two numbers that appear only once .

And because the question requires that returnSize Change to a number that appears only once , Here's the easy part , Just two .

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    *returnSize = 2;
    int *arr=(int*)malloc(sizeof(int)*2);
    int n = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        n ^= nums[i];
    }

	// follow-up ...
}

Now we have n, How do you know next n What are the two numbers ？
Take example 1 in the title as an example , Now? n The value of is 7（0111）：

And we found a rule , Is that if n One of them is 1, That must be between these two numbers , One of them is 1, One of them is 0, To make n This bit of is equal to 1.
So we thought of a way to find these two numbers ：

stay n From right to left in the binary bits of , Find the first one as 1 Number of digits , Then write down this bit as j, And then nums All the numbers in are judged in turn , If in j Position as 1 Then put it into an array , by 0 Then put it into another array . Finally, XOR the two arrays respectively , You can work out these two numbers ！

Take example 1 here as an example , Let's find out from above n be equal to 0111, So the first one is 1 It's just right. It's the first , And then put nums The first bit in the array is 1 Put it in an array , by 0 And put it in another array .

	int j = 0;// Used to store the first one as 1 Number of digits 
    while(n > 0)
    {
    
        if(((n>>j) & 1) != 1)
        {
    
            j++;
        }
        else
        {
    
            break;
        }
    }

    int arr0[10000] = {
    0};
    int n0 = 0;
    int arr1[10000] = {
    0};
    int n1 = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        if(((nums[i]>>j) & 1) == 0)
        {
    
            arr0[n0] = nums[i];
            n0++;
        }
        else
        {
    
            arr1[n1] = nums[i];
            n1++;
        }
    }    

Finally, find the two numbers in the two arrays , Because these two numbers have been separated into two arrays .

	int tmp0 = 0;
    int tmp1 = 0;
    for(int i = 0; i < n0; i++)
    {
    
        tmp0 ^= arr0[i];
    }
    for(int i = 0; i < n1; i++)
    {
    
        tmp1 ^= arr1[i];
    }

    arr[0] = tmp0;
    arr[1] = tmp1;
    return arr;

Pass through ！
Complete code ：

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    *returnSize = 2;
    int *arr=(int*)malloc(sizeof(int)*2);
    int n = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        n ^= nums[i];
    }

    int j = 0;// Used to store the first one as 1 Number of digits 
    while(n > 0)
    {
    
        if(((n>>j) & 1) != 1)
        {
    
            j++;
        }
        else
        {
    
            break;
        }
    }

    int arr0[10000] = {
    0};
    int n0 = 0;
    int arr1[10000] = {
    0};
    int n1 = 0;
    for(int i = 0; i < numsSize; i++)
    {
    
        if(((nums[i]>>j) & 1) == 0)
        {
    
            arr0[n0] = nums[i];
            n0++;
        }
        else
        {
    
            arr1[n1] = nums[i];
            n1++;
        }
    }    

    int tmp0 = 0;
    int tmp1 = 0;
    for(int i = 0; i < n0; i++)
    {
    
        tmp0 ^= arr0[i];
    }
    for(int i = 0; i < n1; i++)
    {
    
        tmp1 ^= arr1[i];
    }

    arr[0] = tmp0;
    arr[1] = tmp1;
    return arr;
}

Don't forget to praise after learning ！