LEETCODE —— 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?

#-------------------------------------------------------------------------------
# Name:        module1
# Purpose:
#
# Author:      ScottGu<[e-mail], [e-mail]>
#
# Created:     13/11/2014
# Copyright:   (c) ScottGu<gu.kai.66> 2014
# Licence:     <your licence>
#-------------------------------------------------------------------------------

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        self.__init__()
        for num in A:
            if(self.dict.has_key(num)):
                self.dict[num]+=1
            else:
                self.dict[num]=1
        for p in self.dict.items():
            if(p[1]==1):
                return p[0]

    def __init__(self):
        self.dict={}

def main():

so=Solution()
arr=[1,1,2,2,3,3,4,4,5,6,6]
print arr
print so.singleNumber(arr)
arr=[1,2,2,3,3,4,4,5,6,6]
print arr
print so.singleNumber(arr)
arr=[1,1,2,3,3,4,4,5,6,6]
print arr
print so.singleNumber(arr)

arr=[1,1,2,2,3,3,4,4,5]
print arr
print so.singleNumber(arr)

arr=[1,0,1]
print arr
print so.singleNumber(arr)

arr=[1,0,0]
print arr
print so.singleNumber(arr)