https://leetcode.com/problems/single-number/

Solution:

• Time complexity: O(n)

• Space complexity: O(1)

It is not hard to find non-duplicate elements. Even if the time complexity of using a Linear List is the same, there are many ways to do it.

However, it isn't easy because the algorithm can only use constant extra space. That is to say. We cannot achieve it with the help of external space.

So, what's a good way to solve it?

The answer is: the XOR operator in bitwise operations.

Let me briefly describe the common sense of XOR:

• Any number XOR with itself is 0:

a ^ a = 0

• Any number XOR with 0 is itself:

a ^ 0 = a

• The XOR operation is commutative and associative:

a ^ b ^ a = a ^ a ^ b = 0 ^ b = b

Code:

class Solution {
    func singleNumber(_ nums: [Int]) -> Int {
        var result = 0
        for num in nums {
            result ^= num
        }
        return result
    }
}

Follow me on:

(Foks) Hui Wang's LinkedIn