136. Single Number

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?

My Solution

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        r = 0
        for i in range(len(nums)):
            r ^= nums[i]
        return r

Reference (转)

def singleNumber1(self, nums):
    dic = {}
    for num in nums:
        dic[num] = dic.get(num, 0)+1
    for key, val in dic.items():
        if val == 1:
            return key

def singleNumber2(self, nums):
    return 2*sum(set(nums))-sum(nums)

def singleNumber3(self, nums):
    return reduce(lambda x, y: x ^ y, nums)

def singleNumber4(self, nums):
    return reduce(operator.xor, nums)