preface

This article is participating in the nuggets team number online activity, click to see the dachang spring recruiting positions.

The title

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:1The sample2:
Copy the code

Example 2:

Input:4.1.2.1.2] output:4
Copy the code

Answer key

It looks simple, and there’s a lot of ways we could do it, but if they want to use no extra space, linear time complexity, this is a little harder to think of.

First of all, what would I have done without this limitation?

Method one: Use sort

So we sort the array, we sort the array, and then because there’s only one tree that happens once, this number has to be in the odd digit, and as long as it’s in the odd digit and it’s not equal to the next digit, that’s what we’re going to return.

However, this method does not meet the time and space requirements proposed by the title.

So we came up with xOR operators.

Method 2: Use xOR.

What are the rules for xOR?

The same number xor is 0, and any number xor is any number.

AC code

/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function(nums) {
    let ans = 0;

    for(let i = 0; i < nums.length; i++){
        ans ^= nums[i];
    }
    
    return ans;
};

Copy the code

conclusion

The key of this problem is the bit operator xor! If you can’t think of it, you can’t solve it, so whenever they say no extra space, we have to go to the bitwise operator.