Given an array of integers, every element appears twice except for one. Find that single one.
Note:Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
题目分析:
给定一个数组,其中每个元素都重复了两次,只有一个元素出现了一次,找出这个元素.
要求T(n) = O(n),并且不开辟新的内存空间(C++无法做到，姑且认为 S(n) = O(1)).
解:
XOR相关知识：
A^A = 0
A^0 = A
AAB = B
且XOR满足交换律和分配律
Solution：
int singleNumber(vector<int>& nums)
{
for (int i = 1; i < nums.size(); i++)
nums[0] ^= nums[i];
return nums[0];
}
T(n) = O(n)
S(n) = O(1)
