[Leetcode] 136. Single Number

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

Note:

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

Example 1: Input: [2,2,1] Output: 1

Example 2: Input: [4,1,2,1,2] Output: 4

这道题比较直观的做法就是用hashmap，然后循环找到value是一个的就行了。但是follow up要求的是空间为1，那么hashmap就不行了。这里面要用异或xor操作，当一个数字两次被xor，那么相当于没有对其操作，，因为相同的数字两次xor对原来的数字就没有影响。下边这是几个非常有代表性的解法

def singleNumber1(self, nums):
    dic = {}
    for num in nums:
        dic[num] = dic.get(num, 0)+1
    for key, val in dic.items():
        if val == 1:
            return key

def singleNumber2(self, nums):
    res = 0
    for num in nums:
        res ^= num
    return res
    
def singleNumber3(self, nums):
    return 2*sum(set(nums))-sum(nums)
    
def singleNumber4(self, nums):
    return reduce(lambda x, y: x ^ y, nums)
    
def singleNumber(self, nums):
    return reduce(operator.xor, nums)

补充知识， 位操作：

a = 0011 1100

b = 0000 1101

[Leetcode] 136. Single Number

原文：https://www.cnblogs.com/codingEskimo/p/12640417.html