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

数组中只出现一次的数字

知识点：

题目描述

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

解题思路

思路一

1、异或思想，一个数与自己异或为0，一个数与0异或为自己 2、由于其它数字两两相同，所以所有数异或则得到这两个不同数的异或结果。取这个结果的第一个1作为标志位 3、这个标志的1，必须是：这两个数在该位一个为0，一个为1 4、这样可以将数组分为两组，一组在该标志位为1，一组在该标志位为0，这两个不同数字分别在这两组内 5、将两组内的数分别异或，得到两个结果则为这两个不同的数

思路二

哈希思想，所有数放入map，最后看哪个key对应的value只有一个

代码

    def FindNumsAppearOnce(self, array):
        # write code here
        if array is None:
            return []
        xorResult = array[0]
        for i in range(1, len(array)):
            xorResult = xorResult ^ array[i]
        if xorResult == 0:
            return []

        index = 0
        while (xorResult & 1) == 0:
            xorResult=xorResult >> 1
            index += 1

        a = b = 0

        for itemArray in array:
            if self.isBit(itemArray, index):
                a = a ^ itemArray
            else:
                b = b ^ itemArray

        return [a, b]

    def isBit(self, data, index):
        data=data >> index
        return data & 1

这里