Leetcode-260题:Single NumberIII

题目

Given an array of numbers nums, in which exactly two elements appear only once and all the other elements appear exactly twice. Find the two elements that appear only once.

For example:

Given nums = [1, 2, 1, 3, 2, 5], return [3, 5].

思路

所有数字的异或值就是那两个数字的异或值，设这个值的最右端的１为第i位，那么根据第i位是否为１可将所有数字分为两类，对每一类再进行一次异或就得到这两个值。更详细的内容可参考<<剑指offer>>

代码

class Solution(object):
    def singleNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        temp = 0
        for num in nums:
            temp ^= num
        i = 0
        while (temp & 1) == 0:
            i += 1
            temp = temp >> 1
        a1 = []
        a2 = []
        for num in nums:
            if num & (1<<i) == 0:
                a1.append(num)
            else:
                a2.append(num)
        t1 = 0
        for num in a1:
            t1 ^= num
        t2 = 0
        for num in a2:
            t2 ^= num
        return [t1,t2]