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): return sum(list(set(nums)))*2 - sum(nums)思路二：利用異或的自反性與交換律。(a^a)^(b^b)^(c^c)^……^z=z.因?yàn)閍^a=b^b=0.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)
新聞熱點(diǎn)
疑難解答
網(wǎng)友關(guān)注
