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?

 

分析：给出一组数组，每个元素都出现两次，只有一个元素只出现一次。要求不需要额外的存储空间，时间复杂度是O(n)。我们想到一个性质：任何一个数字与自己异或的结果都为0，故可以想到数组中一个元素出现两次，只有一个出现一次。我们可以使用异或的思想来解决这题。例如{a,b,c,a,b,c,d}使用中间变量Temp,可以得出下面公式Temp=Temp^a^b^c^a^b^c^d=Temp^(a^a)^(b^b)^(c^c)^d=Temp^d.

代码实现如下：

class Solution {public:    int singleNumber(int A[], int n) {        int result=0;        for(int i=0;i

python实现的道理也一样：最近在看python，忍不住用python写了一下，练练手。

class Solution:    # @param A, a list of integer    # @return an integer    def singleNumber(self, A):        result=0        for a in A:            result^=a        return result