题目截图.png

题目翻译：

给定非空整数数组，除了一个元素之外，每个元素都出现两次。找到那个只出现一次的元素。

Note：

算法应该具有线性运行时复杂度。能在不使用额外内存的情况下实现它吗？

题目思路1：

使用collections模块的Counter()类统计每个元素出现的次数，将其保存在字典{element, count}中。遍历字典中每个元素element对应的count，若count == 1， 则返回该element。

代码如下：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        import collections
        key_dict = {}
        key_dict = collections.Counter(nums)
        for element, count in key_dict.items():
            if count == 1:
                return element

算法的时间复杂度为：O(n)。但是key_dict占用了额外的内存。

题目思路2：

若想要不消耗额外的内存，则应该采用异或操作。在进行异或操作之前，需要将给定的数字转化为二进制形式，然后相异为1，相同为0.因此，将list内部的元素都进行异或操作，那么剩下的那个元素应该就是只出现一次的元素。

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

参考链接：

python 运算符： http://www.runoob.com/python/python-operators.html

PS

新手写LeetCode，新手写文章，若有问题或者错误请告知，谢谢。