136. Number only show once

tags

trick, BinaryOperation

source

leetcode-cn

Edge Cases

Solution - O(N) Space

1. use set, when number in set, delete it; not in set, add it. after one iteration, left is the number only shows once
2. hashset, store number showing times
3. set store all numbers, get sum1 from set, sum1 * 2 - sum(array) = answer

Complexity

• time: O(N)
• space:

Solution - BinaryOperation

a xor 0 = a
a xor a = 0
a xor b xor c = a xor c xor b = a xor (c xor b)

iterate whole array, xor every item, left is answer

Complexity

• time: O(N)
• space: O(1)