136. Single Number

Description

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

Solutions

1. Bit Manipulation

　　知道用异或做还是蛮简单的。

# Time: O(n)
# Space: O(1)
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        n = len(nums)
        pivot = nums[0]
        for i in range(1, n):
            pivot = pivot ^ nums[i]
        return pivot
# 16/16 cases passed (80 ms)
# Your runtime beats 99.13 % of python3 submissions
# Your memory usage beats 9.84 % of python3 submissions (15.2 MB)

　　如果不取第一个数，可以用与零异或。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for num in nums:
            res ^= num
        return res
# Runtime: 68 ms, faster than 69.68% of Python online submissions for Single Number.
# Memory Usage: 13.6 MB, less than 72.07% of Python online submissions for Single Number.

2. Hash Table

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {}
        for num in nums:
            dic[num] = dic.get(num, 0)+1
        for key, val in dic.items():
            if val == 1:
                return key
# Runtime: 72 ms, faster than 62.26% of Python online submissions for Single Number.
# Memory Usage: 15 MB, less than 5.20% of Python online submissions for Single Number.

3. 其他神奇操作

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return 2*sum(set(nums))-sum(nums)
# Runtime: 68 ms, faster than 69.68% of Python online submissions for Single Number.
# Memory Usage: 13.8 MB, less than 39.18% of Python online submissions for Single Number.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(lambda x, y: x ^ y, nums)
# Runtime: 88 ms, faster than 33.36% of Python online submissions for Single Number.
# Memory Usage: 13.5 MB, less than 92.87% of Python online submissions for Single Number.

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return reduce(operator.xor, nums)
# Runtime: 88 ms, faster than 33.36% of Python online submissions for Single Number.
# Memory Usage: 13.6 MB, less than 66.20% of Python online submissions for Single Number.

References

136. Single Number