题解 | #数组中只出现一次的两个数字#

方法一：哈希表 暴力

1.遍历数组将元素存入哈希表对应次数为1

2.若元素已经存在于哈希表则其次数+1

3.遍历哈希表，将次数为1的元素存入res中，并升序输出

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        # 暴力
        hash_temp = dict() # 创建哈希表
        for i in array:
            count = 1
            if i not in hash_temp:
                hash_temp[i] = 1
            else:
                count += 1
                hash_temp[i] = count
        res = []
        for j,k in enumerate(hash_temp):
            if hash_temp.get(k) == 1:
                res.append(k)
        res.sort()
        return res

时间复杂度 O(n) 空间复杂度 O(n) 排除

方法二：位运算 转自大佬

算法流程：

1. 遍历数组执行异或：异或运算有个重要的性质，两个相同数字异或为 0
2. 设整型数组[a,a,b,b,...,x,y] ，对数组中所有数字执行异或，得到的结果为x⊕y
3. 循环左移计算 m：根据异或运算定义，若整数x⊕y 某二进制位为 11 ，则 x 和 y 的此二进制位一定不同。换言之，找到x⊕y 某为 1 的二进制位，即可将数组拆分为上述的两个子数组。根据与运算特点，可知对于任意整数 a有：

若a&0001=1 ，则a的第一位为1；

若a&0010=1 ，则a的第二位为1；以此类推

12. 因此，初始化一个辅助变量 m = 1，通过与运算从右向左循环判断，可 获取整数x⊕y 首位1 ，记录于 m 中
13. 拆分数组为两个子数组，分别遍历两个子数组执行异或： 通过遍历判断两个数组中各数字和 m做与运算的结果，可将数组拆分为两个子数组，并分别对两个子数组遍历求异或，则可得到两个只出现一次的数字
14. 返回只出现一次的数字 x, y 即可。、

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        # write code here
        # 位运算
        x, y, n, m = 0, 0, 0, 1
        for arr in array: # 1.遍历异或整个数组
            n ^= arr
        while n & m == 0: # 2. 循环左移计算m
            m <<= 1
        for arr in array: # 3. 划分数组
            if arr & m : 
                x ^= arr # 4.当 arr & m == 0
            else:
                y ^= arr # 4.当 arr & m != 0
        if x < y:
            return [x, y]
        else:
            return [y, x]