[剑指Offer]数组中只出现一次的数字

题目描述

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

解题思路

方法二：考虑时间复杂度。考虑该问题的简化版：一个整型数组里除了一个数字之外，其他的数字都出现了偶数次。由于每个数和它自身的异或值都为0，所以将数组中所有的数异或一遍即为出现了一次的那个数字的二进制表示。
如果对于本问题，能够将原数组拆分成两个子数组，使得每个数组包含一个只出现一次的数字，而其他数字都成对出现两次，就可以找出这两个数字。
解法：对于整个数组异或一遍，那么该异或值即为两个出现一次的数字的异或值，按照其中某一位为1（此处选择最高位）将原数组分为两个子数组即可。拆分的思路为：找出最高位为1所需右移的位数，将所有数字右移，再与1按位与运算，为1分到一组，为0分到另一组。

代码

Python(2.7.3)

方法一：不考虑复杂度

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

运行时间：23ms
占用内存：5716k

方法二：考虑复杂度

# -*- coding:utf-8 -*-
class Solution:
    # 返回[a,b] 其中ab是出现一次的两个数字
    def FindNumsAppearOnce(self, array):
        # write code here
        tmp = 0
        for i in array:
            # 第一遍异或运算
            tmp ^= i
        high_idx = -1
        while tmp:
            # 找出tmp中1的最高位
            tmp = tmp >> 1
            high_idx += 1
        a, b = 0, 0
        for i in array:
            # 分组异或
            if self.isBit1(i, high_idx):
                a ^= i
            else:
                b ^= i
        return [a, b]

    def isBit1(self, num, index):
        # 判断num的第倒数index+1位是否为1
        num = num >> index
        return num & 1

运行时间：34ms
占用内存：5732k