Leetcode-136- number that appears only once (solve with XOR)

Title Description

Given an array of non-empty integers , Except that an element only appears once , Each of the other elements occurs twice . Find the element that only appears once .

explain ：

Your algorithm should have linear time complexity . Can you do this without using extra space ？

Example 1:
Input : [2,2,1]
Output : 1

Example 2:
Input : [4,1,2,1,2]
Output : 4

Tips： Solve with XOR

Basic knowledge of

The characteristic of XOR ：
1. Law of constancy ：A ^ 0 = A
2. Zero rate ：A ^ A = 0
3. Commutative law ：A ^ B = B ^ A
4. Associative law ：(A ^ B) ^ C = A ^ (B ^ C)

Application point

• You can judge whether the two values are equal by XOR ：a ^ b == 0, be a And b equal .

• Use XOR to eliminate numbers that appear twice

Their thinking

Use the zeroing rate of XOR , Make all the numbers that appear twice become 0, And the number and... That only appear once 0 The operation can still keep itself . Let's look at the following example .
Let's say all arrays are ：abcbcda
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d

Code

Solution 1 ：

My first spicy chicken solution , Leng find .
High time complexity , The last test case failed .

def singleNumber(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    validated = []
    for i, num in enumerate(nums):
        if num in validated:
            continue
        single = True
        for j in range(len(nums) - i - 1):
            print(num, nums[j+i+1])
            if num == nums[j + i + 1]:
                validated.append(num)
                single = False
        if single:
            print(num)
            break

Solution 2 ： Excellent algorithm ：

def excellent_singleNumber(nums):
    a = 0
    for num in nums:
        a ^= num
        
    return a

It was amazing when I first saw this algorithm ……

Reference resources ：
Leetcode-136- A number that appears only once