题目描述

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

你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。

 

示例 1 ：

输入：nums = [2,2,1]

输出：1

示例 2 ：

输入：nums = [4,1,2,1,2]

输出：4

示例 3 ：

输入：nums = [1]

输出：1


提示：

1 

分析

解法一： 使用哈希表

这道题如果不要求空间复杂度，那么可以直接使用辅助空间，比如哈希表、集合、数组等，下面给出使用哈希表的实：我们遍历这个数组，然后将出现的数作为key，将出现的次数记成value，当遍历一遍过后就可以得到一个数字和这个数字出现次数的哈希表：{数字a: 数字a出现的次数, 数字b: 数字b出现的次数, ...},最后遍历字典返回value为1的key即可！

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 方法一：哈希表
        map = dict()
        for num in nums:
            if map.get(num):
                map[num] += 1
            else:
                map[num] = 1
        for key, value in map.items():
            if value == 1:
                return key

解法二：使用位运算

算法思想：因为：

0 亦或 0 = 0
0 亦或 1 = 1
1 亦或 0 = 1
1 亦或 1 = 1

简单理解，只要相同，那么结果就是0，只要不相同，结果就是1.

数字也是一样：

# 4 和 1 进行亦或
0100
0001
----
0101 = 5

# 4 和 1 亦或的结果再进对1行亦或:
0101
0001
----
0100 = 4

上诉例子可以很明白地看出来，只要一个列表里面有偶数个两个相同的元素，那么亦或之后肯定是0，又0和谁亦或得到谁，于是我们可以利用这个特性，只需要将列表中所有的元素进行一遍亦或操作即可，看代码：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        # 方法二：使用位运算
        return reduce(lambda x, y: x ^ y, nums)

总结

能想到这方法的人太厉害啦。

如果想了解更多关于这道题为什么使用亦或操作，可以参考：

作者：力扣官方题解
链接：https://leetcode.cn/problems/single-number/solutions/242211/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。