1、题目

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

2、解法

from functools import reduce
from typing import List

class Solution:
    def containsDuplicate(self, nums: List[int]) -> bool:

        # # 遍历法：遍历，当某元素个数等于1时返回该元素
        # for i in range(len(nums)):
        #     if nums.count(nums[i]) == 1:
        #         return nums[i]

        # # 集合法：集合拿到每个元素*2 减去 原来数组的和
        # return 2 * sum(set(nums)) - sum(nums)

        # # 位运算法：
        return reduce(lambda x,y: x^y,nums)

if __name__ == '__main__':
    nums = [2,2,1]
    a = Solution()
    print(a.containsDuplicate(nums))

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

3、位运算

程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算说穿了，就是直接对整数在内存中的二进制位进行操作。
这道题的真实目的其实是在考察我们能否用线性的时间和常量的空间来完成。
如何实现呢？答案呼之欲出，我们应该使用位运算其中的异或运算。