Elementary Algorithms (Question 5)

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

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

Their thinking

Since we're trying to find the one in an array that doesn't repeat itself, that only shows up once, the easiest way to solve it with xOR, xor has the following characteristics1^1=0;
1^0=1;
0^1=1;
0^0=0; You convert numbers to binary for comparison0000= =0
||||
0010= =2
||||
0010= =2

0010= =2
||||
0010= =2
||||
0010= =2So all we need to do is set an initial value and compare that to the last value returned by the assignment/ * * *@param {number[]} nums
 * @return {number}* /
var singleNumber = function(nums) {
    const length = nums.length;
    let ans = 0;
    for(let i = 0; i < length; i++){
        ans ^= nums[i];
    }
    return ans
};
Copy the code