【LeetCode15】只出现一次的数字

今日挑战

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

说明：

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

示例 1:

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

示例 2:

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

先思考一下，后面我会给出一个解题思路～?

图来自网络

因为这道题目规定了不要用到额外的空间，也就是必须要在O(N)的空间复杂度内完成，所以这里使用一个字典来存储统计的结果。

1 ）定义一个字空典。

2 ）依次遍历数组的所有元素，当出现一个新元素时，赋值为1，当这个元素不是新元素的时候，从字典中pop（移除）掉。

3 ）因为只有一个元素出现了1次，其余的元素均出现了2次，所以遍历完所有元素，只会剩下那个“只出现一次“的元素。

Python实现：

def singleNumber(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    hash_table = {}
    for i in nums:
        try:
            hash_table.pop(i)
        except:
            hash_table[i] = 1
    return hash_table.popitem()[0]

配图角色背景介绍

快银（Quicksilver）是美国漫威漫画旗下超级英雄，初次登场于《X战警》（The X-Men）第4期（1964年3月），由编剧斯坦·李和画家杰克·科比联合创造。本名皮特罗·姜戈·马克西莫夫（Pietro Django Maximoff），他的起源故事版本众多，漫画中最新剧情是由吉普赛人姜戈和玛丽所生，小时候和双胞胎姐姐绯红女巫（比快银早出生30秒）一起被高进化者（High Evolutionary）绑架当做实验对象，从而获得了高速移动的能力，后来二人被骗，听信了自己是万磁王的孩子，母亲抛弃了他们，接生的牛头女士把他们交给了吉普赛人夫妇的这个说法。还和姐姐共同加入万磁王领导的变种人兄弟会。后得知真相改邪归正，加入复仇者联盟。

原著的快银十分的强悍，但是在复仇者电影系列中，快银从登场到领盒饭快得有点出乎意料，可能由于他做什么事情都很快导致的o.o,快银在《奥创纪元》中为了拯救鹰眼和一个小男孩被机枪扫射而死。这个死法有点无法理解。