136. Single Number

描述

Given a non-empty 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?

Example 1:

Input: [2,2,1]
Output: 1

Example 2:

Input: [4,1,2,1,2]
Output: 4

解法

使用集合记录状态

使用列表加 count 的方法超时了，于是尝试使用 set 通过。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = set()
        for num in nums:
            if num not in tmp:
                res.add(num)
            else:
                res.remove(num)

        return res.pop()

时间复杂度： $O(n)$。一次遍历即可，判断是否在集合中和添加、移除操作都是 $O(1)$ 复杂度。

空间复杂度： $O(n)$

这种计数的题目还可以考虑使用 counter。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        from collections import Counter
        ct = Counter(nums)

        return ct.most_common()[-1][0]

数学的方法

概念：

$2 \times (a + b + c)−( a + a + b + b + c) = c$

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2 * sum(set(nums)) - sum(nums)

时间复杂度：$O(n + n) = O(n)$。

空间复杂度：$O(n + n) = O(n)$。set 使用了额外空间。

位运算

根据异或操作：

一个数异或 0 是其本身：

$a \oplus 0 = a$

一个数异或其本身是 0：

$a \oplus a = 0$

所以：

$a \oplus b \oplus a = (a \oplus a) \oplus b = b$

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

        return res

时间复杂度：$O(n)$

空间复杂度：$O(1)$