#82 Single Number

题目描述：

Given 2*n + 1 numbers, every numbers occurs twice except one, find it.

Have you met this question in a real interview?  Yes Example

Given [1,2,2,1,3,4,3], return 4

Challenge 

One-pass, constant extra space.

题目思路：

这题我就用了很多人用的bit manipulate的方法，用异或来解决。因为当两个数相同的时候，异或返回0，所以把A中所有数都异或一遍，最后得到的数就是那个单身狗，因为没有别的数跟它异或成0。

Mycode（AC = 10ms）：

class Solution { public: /** * @param A: Array of integers. * return: The single number. */ int singleNumber(vector<int> &A) { // write your code here if (A.size() == 0) return 0; else if (A.size() == 1) { return A[0]; } else { int bitm = A[0]; for (int i = 1; i < A.size(); i++) { bitm ^= A[i]; } return bitm; } } };