Make writing a habit together! This is the third day of my participation in the “Gold Digging Day New Plan · April More text Challenge”. Click here for more details.

preface

The numbers that appear only once in question 136 are as follows:

Given an array of non-empty integers, each element appears twice except for one element. Find the element that appears only once.

Description:

Your algorithm should have linear time complexity. Can you do it without using extra space?

Example 1:

Input: [2,2,1] output: 1Copy the code

A, thinking

The title is short, and the goal is to find an element that occurs only once (that element is unique). A simple idea is as follows:

1. The first time through the group, count the number of occurrences for each element
2. Iterate over the results of the statistics again to find the element that appears once
3. Return the element

According to the above ideas, I implemented a code as shown in the figure below:

Obviously this method can be achieved, but the defeat rate is not too high.

So the hash table above is obviously not going to satisfy the problem of not using extra space, so how do we do that?

Exclusive or operation

I also summarized the following ideas after seeing the official solution of the problem, and did not think of using xOR operation to solve the problem.

Xor operation has the following three characteristics:

1. Any number xor with 00 will still be the same number, i.eA radius 0 = a
2. Any number xor with itself, the result is 0, i.eA radius of a = 0
3. Xor operations satisfy commutative and associative laws, i.eA radius b the radius of a = b radius radius radius a = b = b (a radius a) radius 0 = b

We know that there is only one unique element in the array, so let’s assume that the array looks like this: ababcb

Let’s simply switch places and put the same things together

Then the xOR operation of all elements is as follows: A ⊕ A ⊕ B ⊕ B ⊕ B ⊕ C, and the calculation process is as follows:

And you end up with c.

To sum up: all we need to do is xor all the elements in the array, and the same elements will be eliminated automatically.

Second, the implementation

The implementation code

After knowing the idea, the implementation is relatively simple

public int singleNumber(int[] nums) {
    int ret = 0;    // The initial value of 0 has no effect on the result
    for (int n : nums){
        ret = ret ^ n;
    }
    return ret;
}
Copy the code

The test code

public static void main(String[] args) {
    int[] nums = {4.1.2.1.2};
    new Number136().singleNumber(nums);
}
Copy the code

The results of

Third, summary

Today, I have a deeper understanding of xOR operation. I never thought I could use it to find single numbers. It’s really an eye-opener!

Thank you to see the end, very honored to help you ~♥

If you think my writing is good, you might as well give me a thumbs-up! If you have any questions, please see the comments section