Single Number 普通解及最小空间解（理解异或）

佚名 5年前 (2019-09-20) 算法 2164人围观抢沙发百度已收录

原题目

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Note:

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

普通解

刚看到的这个题目第一时间想到的就是a[i]++，最后找出a[i]==1的方法，但一方面python的数组操作没有那么灵活，再就是负数部分不好处理，想了一会儿比较好的方法应该是有一个容器，第一次遇到该值时将其放进去，第二次遇到时就将该值取出，这样整个输入结束后容器中就只剩下我们要的single number了，时间复杂度也只是O(n)，列表在不知道索引的情况下不方便移除指定数据，而set中的remove方法则刚好适合，所以最终代码如下：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        single = set()
        
        for num in nums:
            if num in single:
                single.remove(num)
            else:
                single.add(num)
        for num in single:
            return num

不使用额外空间的解

提示里面提醒我们能不能不使用额外的内存就实现它，在不增加时间的情况下百思不得其解，后来看到了讨论区大神的解答才知道可以用异或的方法来做，也更新了我对异或的理解（原本以为异或只适用于0和1）。首先介绍下异或，异或操作最基本的就是

0 XOR n = n
n XOR n = 0

同时异或还具有一大特点就是其可交换性，即

a xor b xor c 三者可以任意交换结果不变

所以将所有输入的值异或再交换，即可得到single number,代码如下

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        xor = 0
        for i in range(len(nums)):
            xor ^= nums[i]
        return xor