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

法一：哈希方法

与#第一个只出现一次的字符#的思路类似。先用哈希表记录每个数出现的频率，然后遍历哈希表，将只出现一次的数加入答案。 https://blog.nowcoder.net/n/6aa6f3ed254041a88572510af837616e

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def FindNumsAppearOnce(self , array: List[int]) -> List[int]:
        #统计每个字符出现的次数
        mydict={}
        for i in array:
            if i not in mydict:
                mydict[i]=1
            else:
                mydict[i]=mydict[i]+1
                 
        #记录两个只出现一次的字母
        mylist=[]
        for i in array:
            if mydict[i]==1:
                mylist.append(i)
                
        if mylist[0]>mylist[1]:
            mylist[0],mylist[1]=mylist[1],mylist[0]
        return mylist     

时间复杂度：O(n)，其中n为数组长度，两次单独的遍历数组每个元素

空间复杂度：O(n)，哈希表的长度应该为(n−2)/2

法二：位运算（参考牛客题解官）

思路：

利用异或运算性质，满足交换率，且相同的数字作异或会被抵消掉，比如：a⊕b⊕c⊕b⊕c=a，且任何数字与0异或还是原数字，放到这个题目里面所有数字异或运算就会得到a⊕b。

题目要求得到a和b分开的结果。采用的做法是，将数组分成两部分，一部分为a⊕d⊕c⊕d⊕c=a，另一部分为b⊕x⊕y⊕x⊕y=b的样式，让a与b完全分开，且另外的成对数字正好在一个组。具体做法是:

（1）a⊕b结果的二进制从最低位开始遍历，总能找到二进制位为1的位置（具体做法是，1逐次左移位，和a⊕b做与运算，直到结果不等于0，即找到a⊕b结果中二进制位为1的位置）。异或结果为1说明a和b在该位上数字不同。

（2）因为两个数字不相同，我们就以这一位是否为1来划分上述的两个数组，相同的数字自然会被划分到另一边，而a与b也会刚好被分开。（具体做法是，遍历整个数组，每个数和划分数做与运算，等于0的是一组，不等于0的另一组）

代码参见题解区。

时间复杂度：O(n)，遍历两次数组，找到两个数不相同的第一位，循环为常数次

空间复杂度：O(1)，常数级变量使用，无额外辅助空间