面试题56：数组中只出现一次的数字

题目一：
一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。时间复杂度为O(n), 空间复杂度O(1)。

思路：
这道题比较难，需要分步骤考虑，假设题目为只有一个数字出现了一次，其他的出现两次，那么可以通过异或来得到结果，相同的两个数字异或结果为0，所以说当逐个异或之后，得出的结果为就为只出现一次的结果。

下面考虑，如何能够把一个数组分成两个每个里面只有一个数字出现一次，其余的都出现两次的子数组。思路如下：将该数组异或按位异或，那么其结果一定不为0，既然不为0一定至少有一位不为0。从右到左，取出第一个不为0的位置，说明那两个不同的只出现一次的值，在这位一定不同，所以按照这个位置上数字为1的是一个子数组，为0的为另一个子数组，然后在分别求出每个子数组里的出现一次的数字，即可解决这道题。

代码实现：

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        #特殊情况
        if len(array)<2:
            return None
        #一般情况
        #得出异或的结果
        Result = 0
        for num in array:
            Result ^=num

        #得到结果中不为1的位置
        index1 = self.FirstOne(Result)

        #按照索引位置10不同分为两个子数组
        res1 = 0
        res2 = 0
        for nums in array:
            if self.IsBit1(nums,index1):
                res1 ^= nums
            else:
                res2 ^= nums
        return [res1,res2]

    #找到从右边起第一个不为0的位置
    def FirstOne(self,num):
        index = 0
        while (num&1==0 and index < 32):
            num = num >> 1   #右移一位
            index +=1
            print("enter")
        return index

    #判断对应位置是否为1
    def IsBit1(self,num, index):
        num = num >> index   #右移index位
        return (num&1)

提交结果：

题目二：
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

思路：
利用字典

代码实现：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        #使用字典来完成操作
        dicNum = {}
        for i in nums:
            if i not in dicNum:
                dicNum[i] =1
            else:
                dicNum[i] +=1
        for key in dicNum:
            if dicNum[key]==1:
                return key

提交结果：