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?

Subscribe to see which companies asked this question.

答案

思路一：只有一個(gè)不重復(fù)，取nums的set得到不重復(fù)的list，然后求和兩倍list減去原來(lái)的nums就得到不重復(fù)的那個(gè)。

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

思路一速度遠(yuǎn)快于思路二，但思路一是利用python中set的特性：set中沒(méi)有重復(fù)元素。所以僅在python中可用。思路一除了set（）操作，sum操作的時(shí)間復(fù)雜度為o(n)。思路二需要遍歷所有元素，每次遍歷需要異或操作，時(shí)間復(fù)雜度為o(異或的時(shí)間復(fù)雜度*n)