2.只出现一次的数字

题目描述

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

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

示例 1:

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

链接：https://leetcode-cn.com/problems/single-number

方法1、集合set

执行用时：32 ms

时间复杂度：O()

空间复杂度：O(n)，其中 n 是数组长度。

思路总结：使用集合存储数字。遍历数组，如果集合中存在该数，删除；如果不存在，加入。最后只剩下只出现一次的数，返回。

注意：利用set不能放重复元素的特性来做

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]  [2,2,1]
        :rtype: int  暴力解法    1
        """
        s = set()
        for i, num in enumerate(nums):
            if num in s:
                s.remove(num)
            else:
                s.add(num)
        l=list(s)  # 集合转换为列表是读取集合元素的必要步骤
        return l[0]

方法2、哈希表

执行用时： 28ms

时间复杂度：O()

空间复杂度：O(n)

思路总结：存入哈希表，key为数组的值，value为出现的次数。最后取出哈希表中次数（value）为1的key。

注意：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]  [2,2,1]
        :rtype: int  哈希表     1
        """
        hashtable = dict()
        for i, num in enumerate(nums):
            if num in hashtable:
                hashtable[num] += 1
            else:
                hashtable[num] = 1
        for j in hashtable:
            if hashtable[j]==1:
                return j
        return 0

方法3、位运算，异或运算 ⊕

执行用时： 24ms

时间复杂度：O(n)

空间复杂度：O(1)

思路总结：自身异或=0，与0异或=本身。重复的两个数先两两异或=0；再和只出现一次的数异或=只出现一次的数本身。

注意：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]  [2,2,1]
        :rtype: int  异或     1
        """
        return reduce(lambda x,y:x ^ y, nums)

reduce()，对所有元素进行累积

方法4、求和相减

执行用时： ms

时间复杂度：O()

空间复杂度：O()

思路总结：数组数据存入一个新的集合(集合不可重复)。对集合所有数据求和，再×2倍；对原数组所有数据求和。即set*2-list=只出现一次的数据。

注意：

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]  [2,2,1]
        :rtype: int   求和相减    1
        """
        s = set(nums)
        return sum(s)*2-sum(nums)