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.

答案

思路一：只有一個不重復，取nums的set得到不重復的list，然后求和兩倍list減去原來的nums就得到不重復的那個。

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

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