题目

难度：★☆☆☆☆
类型：数组

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

解答

方案1：统计次数

我们准备一个字典，字典的键是列表中出现过的数字，值是该数字出现的次数，遍历数组统计每个数字出现的次数，最后返回出现过一次的数字即可。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        count = {}                  # 定义字典
        for num in nums:            # 遍历数组
            if num in count:        # 如果字典中存在当前记录
                count[num] += 1     # 次数 + 1
            else:                   # 否则
                count[num] = 1      # 当前数加入到字典中，且出现次数为1
        count = {v: k for k, v in count.items()}    # 字典键值交换
        return count[1]             # 返回出现一次的数字

方案2：列表

准备一个列表，遍历数组，当前数字不在列表中时，加入列表，如果在列表中，则弹出列表中的该数，则最后只有出现过奇数次的数字留在列表中，返回该数即可。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        temp = []                   # 定义空列表
        for num in nums:            # 遍历数组
            if num in temp:         # 如果列表中存在当前数
                temp.remove(num)    # 移除
            else:                   # 否则
                temp.append(num)    # 当前数加入到列表
        return temp[0]              # 返回列表中剩下的数字

方案3：巧用异或

异或运算有这样的特性：

1. 交换律：a ^ b == b ^ a

2. 相同数字异或为零：a ^ a == 0

3. 数字异或零为该数字：a ^ 0 == a

根据以上的三条特性，我们可以得到，如果将数组中所有数字用异或符号连接起来，则出现偶数次的数字失效，最终结果为出现奇数次的数字的异或。

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

或者直接用字符串，内存占用多些。

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        return eval('^'.join(map(str, nums)))

如有疑问或建议，欢迎评论区留言~