Leetcode-136-只出现一次的数（用异或来解答）

题目描述

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

说明：

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

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

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

Tips：用异或来解决

基础知识

异或的特性：
1.恒定律：A ^ 0 = A
2.归零率：A ^ A = 0
3.交换律：A ^ B = B ^ A
4.结合律：(A ^ B) ^ C = A ^ (B ^ C)

应用点

• 可以通过异或来判断两值是否相等：a ^ b == 0，则a与b相等。

• 用异或来消除出现两次的数

解题思路

利用异或的归零率，使所有出现过两次的数变为0，而只出现过一次的数与0运算还能保持本身。可以看下面这个例子。
假设所有的数组为：abcbcda
a ^ b ^ c ^ b ^ c ^ d ^ a
= a ^ a ^ b ^ b ^ c ^ c ^ d
= 0 ^ 0 ^ 0 ^ d
= d

代码

解法一：

我第一次的辣鸡解法，楞找。
时间复杂度高，最后一个测试用例没有通过。

def singleNumber(nums):
    """
    :type nums: List[int]
    :rtype: int
    """
    validated = []
    for i, num in enumerate(nums):
        if num in validated:
            continue
        single = True
        for j in range(len(nums) - i - 1):
            print(num, nums[j+i+1])
            if num == nums[j + i + 1]:
                validated.append(num)
                single = False
        if single:
            print(num)
            break

解法二：优秀的算法：

def excellent_singleNumber(nums):
    a = 0
    for num in nums:
        a ^= num
        
    return a

第一眼看到这个算法的时候觉得太惊艳了……

参考：
Leetcode-136-只出现一次的数字