136. Single Number
Given a non-empty array of integers nums,
every element appears twice except for one. Find that single one.
You must implement a solution with a linear runtime complexity
and use only constant extra space.
input: nums=[2,2,1]
output: 1
input: nums=[4,1,2,1,2]
output: 4
input: nums=[1]
output: 1
理解
利用xor的功能，
XOR Truth Table:
|
p
|
q
|
p xor q
|
|
1
|
1
|
0
|
|
1
|
0
|
1
|
|
0
|
1
|
1
|
|
0
|
0
|
0
|
只要比對的數字是偶數次的，
數字就會被歸零。
題目只有說在陣列的數字，最多只會出現兩次。
只有一個數字只會出現一次。
那利用xor比對全部的數，就可以知道唯一的那個數字。
code(cpp)