剑指offer 40. 数组中只出现一次的数字

40. 数组中只出现一次的数字

题目描述
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路
思路一：
遍历数组，对每个元素直接利用python数组的count函数，因为count()也是，等价于遍历数组再计数，所以时间复杂度为，
思路二：
利用字典保存元素出现次数，最后选出字典中value为1的key返回。时间复杂度为
思路二的优化：
由于一个整型数组里除了两个数字之外，其他的数字都出现了两次。当字典中有某个key时，删除这个key，否则这个key的value为1插入字典，时间复杂度为

思路三：
看题解都是用位运算来做的，我觉得这个方法效率比优化后的思路二低一些，时间复杂度介于到之间
位运算，异或思路，反正我是想不到...看了题解和评论才弄懂是怎么一回事。
按位与&，0&1=0 0&0=0 1&0=0 1&1=1
异或^，对位相加，但不进位 1^0=1 1^1=0 0^0=0 0^1=1

一个数与自己异或为0，一个数与0异或为自己

由于其它数字两两相同，所以所有数相互异或则得到这两个不同数的异或结果。
异或的结果有一位为1，这两个不相同的数在该位一个为0，一个为1。按照这个将数组分为两组，一组在该位为1，一组在该位为0，这两个不同数字分别在这两组内。
将两组内的数凉凉异或，因为相同的数会抵消掉，得到的结果就是这两个不同的数。

代码实现
思路一：python数组的count函数

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        nums = []
        for i in range(len(array)):
            if array.count(array[i]) == 1:
                nums.append(array[i])
        return nums

思路二：利用字典保存元素出现次数，只输出次数为1的元素

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        nums_dict = {}
        for i in range(len(array)):
            try:
                nums_dict[array[i]] += 1
            except KeyError:
                nums_dict[array[i]] = 1
        nums = []
        for num in nums_dict:
            if(nums_dict[num] == 1):
                nums.append(num)
        return nums

思路二的优化：再审审题，发现数组中其他的元素出现次数不是1就是2，所以可以继续优化

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        nums_dict = {}
        for i in range(len(array)):
            try:
                del nums_dict[array[i]]
            except KeyError:
                nums_dict[array[i]] = 1
        return nums_dict.keys()

思路三：位运算，异或法

# -*- coding:utf-8 -*-
class Solution:
    def FindNumsAppearOnce(self, array):
        # write code here

        # 将组内元素异或，返回异或后的结果
        def XORarray(array):
            result = 0
            for i in range(len(array)):
                result ^= array[i]
            return result
        # 从低到高找到第一位为1的数
        # 与1(01)按位与&，0&1=0 0&0=0 1&0=0 1&1=1
        # 如果结果是0,则与2(10)按位与,直到找到让结果是1的theNum
        def getFirstBitIs1(num):
            theNum = 0
            while num&theNum == 0:
                theNum += 1
            return theNum

        num = XORarray(array)
        firstBitNum = getFirstBitIs1(num)
        result = [0,0]
        # 分组进行异或
        for i in range(len(array)):
            if array[i]&firstBitNum == 0:
                result[0] ^= array[i]
            else:
                result[1] ^= array[i]
        return result