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

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

示例

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

输出: 4

解析

1)如果这道题没有不使用额外空间的限制,就有很多种解法,用hash记录次数最直接;

2)既然不能使用额外空间,说明要边遍历边计算,而且题目给出的数字很有意思,2m个成对数字,外加1个单的;

3)看到这个条件,应该能唤醒你的远古记录,三个数字的异或运算,得到的就是那个单独的数字。

代码示例

# 逐个遍历异或相加
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res = 0
        for i in nums:
            res = res ^ i
        return res

# reduce简写形式
class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        return reduce(lambda x1,x2 : x1^x2, nums)

执行用时:44 ms, 在所有 Python3 提交中击败了 74.71% 的用户.

本文为 陈华 原创,欢迎转载,但请注明出处:http://edu.ichenhua.cn/read/381