数组中数字出现的次数：数组中只出现一次的一个数字、数组中只出现一

• 异或运算：如果a、b两个值不相同，则异或结果为1。如果a、b两个值相同，异或结果为0。
• 题目一：136. Single Number【 leetcode】
  一个整型数组里除了一个数字之外，其他的数字都出现了偶数次。请写程序找出这一个只出现一次的数字。
  思路：任何一个数字异或它自己都等于0；与0异或都等于它本身

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

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

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        xor = 0
        for i in range(len(array)):
            xor ^= array[i]
        mark = 1
        #找到从低位到高位访问XOR的第一个等于1的那一位
        while xor & mark == 0:
            mark <<= 1
        #然后根据该位是否为1，将数组分成两个子数组,分别取求异或
        res1,res2 =0 ,0
        for i in range(len(array)):
            if array[i]&mark == 0:
                res1 ^= array[i]
            else:
                res2 ^= array[i]
        return [res1,res2]

题目三：
有一个数组，每个数字都出现了3次，除了其中的某一个只出现了1次。找出这个只出现了1次的数字。
思路：这个题的做法是把32位的二进制数进行遍历，统计每个数字的每一位出现的和。因为每个数字出现了3次或者1次，所以如果某一位出现的次数不是3次，那么这个位置一定是因为那个只出现1次的数字导致的。用来保存结果的res是0，因此使用或操作，就能把这个位置的数字变成1.该问题也可以用字典哈希来做，但是那样的话空间复杂度为O(n)

# -*- coding:utf-8 -*-
class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 0
        for i in range(32):
            cnt = 0
            #统计32位中的每一位出现1的次数
            mask = 1 << i
            for num in nums:
                if num & mask:
                    cnt += 1
            #如果该位上出现1的次数不能被3整除，则一定是因为唯一的那个出现一次的数导致的
            if cnt % 3 == 1:
                #保留该位，与res求或运算
                res |= mask
        #以后出现位运算的时候，需要对结果进行判断一下最好。
        # 如果不在这个范围内，说明了结果被认为是无符号的数了，需要减去2 ^ 32
        if res >= 2 ** 31:
            res -= 2 ** 32
        return res