136. Single Number [easy] [python]

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)