Single Number

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

Example

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

Challenge

One-pass, constant extra space.

Solution

Time O(N), Space O(1)
x ^ x=0 和 x ^ 0=x 可将给定数组的所有数依次异或,最后保留的即为结果。

(Single-Number.py) download

class Solution:
    """
    @param A : an integer array
    @return : a integer
    """
    #根据x^x=0 和x^0=x 可将给定数组的所有数依次异或,最后保留的即为结果
    def singleNumber(self, A):
        # write your code here
        sum = 0
        for i in A:
           sum ^= i
        return sum