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

说明：

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

示例 1:

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

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

巧用集合

1
2
3
4
5
6
7
8
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        #首先使用的是集合去除了重复的值,然后进行了加和.因为这个 nums 是奇数个,因为有一个是只出现一次的.因此去除了重复的值后累加乘上2倍,再减掉原来的数组的加和就是剩下的那个没有出现两次的元素的值
        return sum(set(nums))*2-sum(nums)  #这么太牛逼的做法了

异或

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        # 使用异或的方式
        # 相同的数字异或结果是0
        # 任何数字与0异或是自己本身
        ans = 0
        for num in nums:
            ans ^=num
        return ans
    #这里利用就是不管什么数只要是异或两次想相当于没有被异或过,因此使用0作为初始的异或值,出现两次的元素全部被异或掉了
    #出现一次的跟0异或就是自己本身

test

1
2
0^2^3^2
Out[22]: 3