Leetcode daily practice - the number of digits in the offer 56 array of the sword finger

Preface

Wassup guys！ I am a Edison

It's today LeetCode Upper The finger of the sword Offer 56 - I. The number of occurrences of numbers in an array

Let’s get it！

---

---

1. Title Description

An integer array nums Except for two numbers , The other numbers appear twice . Please write a program to find out these two numbers that only appear once .

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

Example 1：

Example 2：

2. Thought analysis

Before I do this question , First of all, we need to understand one thing , be called Exclusive or , What is XOR ？

1. The nature of XOR

a ^ b： Yes, it will a and b Each bit of the binary system of , Figure derived .

The logic of the operation is ： Two numbers correspond to bit position , For the same 0, The difference is 1.

2. The law of XOR

Any number and In itself Exclusive or , The result is 0;

Any number and 0 Exclusive or , The result is In itself ;

3. XOR satisfies the law of exchange .

namely a ^ b ^ c , Equivalent to a ^ c ^ b;

Be careful ： If you have an array , All numbers appear twice , Only one number appears once , You can set the whole array Cyclic XOR , In this way, you can find the number that only appears once .

Ideas

Based on the above Exclusive or Thought , In fact, we just need to divide this array into two parts , At the same time satisfy ：

（1） The same number Be divided into the same part .
 
（2） Two numbers that only appear once Were assigned to different places .

Ideas ：

（1） First, XOR all the numbers in the array , Get the XOR value of two numbers that appear once .
 
（2） Any found in the XOR result is 1 Bit .
 
（3） Group all numbers according to this digit .
 
（4） XOR within each group , Get two numbers .

Realization

Suppose the input array is ： [1,2,10,4,1,4,3,3], The two numbers that only appear once are 2 and 10;

Step 1

The first 1 Step , The first XOR the whole array once , This will definitely get a new number , This new number is The result of two digital XORs that only appear once , That is to say 2 ^ 10 Result ：8, Please remember that 8！

2： 0 0 1 0
10：1 0 1 0
x： 1 0 0 0

Step 2

The first 2 Step ,8 The binary of is ：1000, You can see , This one has 0 Also have 1, So this one 0 And this 1 What do you mean ？

Based on the nature of XOR operation ：0 Express bit Same bit ,1 Express bit Different bits .

（ Exclusive or operation ： If the same digit is the same, it is 0, The difference is 1）

Step 3

The first 3 Step , This is the time , We want to achieve 8 The lowest bit of is 1 A binary number of ！

How to get the lowest binary number ？

It's simple , It only needs x & (-x);

&： Both are 1, The result is 1, Otherwise 0

 Let's calculate first  -x
1、 according to x Binary system , According to the not 
	x：0000 1000
   Take the opposite ：1111 0111 //  Inverse code 

2、+1
	+1：1111 1000 //  Complement code 

 This time we get -x, Next, calculate  x & (-x)
x： 		0000 1000
-x:	    	1111 1000
x & (-x)：	0000 1000

We put this new binary number （0000 1000） Marked as judgmentNum

Step 4

At this time, we can use this Numbers Yes [1,2,10,4,1,4,3,3] This array is grouped .

Let's first look at the two conditions we want to group ：

（1） The same number Be divided into the same part .
 
（2） Two numbers that only appear once Were assigned to different places .

Then how do we meet these two conditions ？

We just need to put and judgmentNum do & After operation is 0 Divide the numbers into a group , Not for 0 It's OK to divide the numbers into another group .

because ：

（1） For the same number that appears twice , Because they are the same , therefore , They and judgmentNum do & The result is the same . such , It's enough Conditions 1;
 
（2） For those two data that only appear once , That is to say 2 and 10 , We can calculate them and judgmentNum Of & result

2:				0000 0010
judgmentNum:	0000 1000
&  result :			0000 0000

10:				0000 1010
judgmentNum:	0000 1000
&  result :			0000 1000

It's obvious ,2 Of & The result is 0, however 10 Of & It didn't turn out to be 0, This ensures that they are divided into different groups

Step 5

Only this and nothing more , We have followed our plan , Put the original array , Disassembled into two arrays we want ;

We only need to disassemble the two arrays , Do a cycle , XOR every element , That's all right. .

3. Comprehensive analysis of

Solution to the problem ：

It is known that ： Two numbers are equal, and the XOR result is 0, A number with 0 The XOR result is equal to itself .
 
So if there is only one number in the array that appears once , Then you only need to XOR all the numbers to get the number that only appears once , There are two numbers that appear once in this question .
 
therefore , The result of all number XORs is the result of the two number XORs that occur only once . So according to this characteristic , We can use grouping To solve this problem .
 
And the grouping should meet two conditions ：1、 Two identical numbers must appear in the same group ;2、 Those two numbers that only appear once must be assigned to different groups .
 
In this way, we XOR these two groups of numbers respectively , You can get two numbers that appear once . that , How should we group them ？
 
for example [4,1,4,6]： The result of all XORs is 1 and 6 Exclusive or Result . Namely 0001 and 0110 The result of XOR is 0111.
 
It's not hard for us to find out , It is easy to allocate the two same numbers in a group , We just need Fix a binary bit , If these two numbers are the same in this binary bit , Let's put it in the same group .
 
But the difficulty is How to allocate two numbers that only appear once to different groups ？
 
Let's move on ,1 and 6 The result of XOR is 0111,0111 In this binary number is 1 What is the implication of the binary bit of ？
 
Analysis is not difficult to know , The binary bit is 1, It means 1 and 6 The number in this binary bit is different . therefore , This is the basis for us to divide two numbers into different groups .
 
because 0111 Yes 3 All binary bits are 1, They are the first 、 Second 、 Third . This means 1 and 6 The binary number of is first 、 Two 、 The number in three digits is Different Of .
 
Let's assume that Take the first binary bit as the division standard .
 
The first binary bit of the number in the array is 1 Of are divided into the first group .
 
The first binary bit of the number in the array is 0 Of is divided into the second group .
 
In this way, the successful will 1 and 6 Divided into different groups , And the same number, for example 4, because 4 and 4 The first binary bit of is necessarily equal , In this way, we can divide two identical numbers into the same group .
 
Finally, you only need to XOR these two groups separately , You can get the answer we need .

4. Code implementation

Interface code

int* singleNumbers(int* nums, int numsSize, int* returnSize){
    
    // 1. Dynamically open up an array newNums, Used to save only two numbers that appear once 
    int* newNums = (int*)malloc(2 * sizeof(int));

    // 2. XOR all the passed arrays ,  And use x Save up , Its x The result is the result of two digital XORs that appear once 
    int i = 0;
    int x = 0; //  The result of exclusive or of the whole array 
    for (i = 0; i < numsSize; ++i) {
    
        x ^= nums[i]; 
    }

    // 3. To calculate the x Which bit of binary bit is 1, use judgmentNum Save up 
    int judgmentNum = 1; // Initial bit 0001
    while ((judgmentNum & x) == 0) {
    
        // If judgmentNum The first binary bit is not 1, will judgmentNum The left one 0010, Then with x Meet each other , Judge judgmentNum Whether the second place is one .
        // Press this cycle , Know where to find it judgmentNum The first one is 1 Binary bit of 
        judgmentNum = judgmentNum << 1;
    }
    

    // 4. According to each number judgmentNum Location , Grouping , A fellow 1 A group of , A fellow 0 A group of 
    int num1 = 0;
    int num2 = 0;
    for (i = 0; i < numsSize; ++i) {
    
        if (nums[i] & judgmentNum) {
    
            num1 ^= nums[i];
        }
        else {
    
            num2 ^= nums[i];
        }
    }

    // 5. Save the found number in the array 
    newNums[0] = num1;
    newNums[1] = num2;
    *returnSize = 2;
    return newNums;
}

Submit results