题目
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].
思路
所有数字的异或值就是那两个数字的异或值,设这个值的最右端的1为第i位,那么根据第i位是否为1可将所有数字分为两类,对每一类再进行一次异或就得到这两个值。更详细的内容可参考<<剑指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]
网友评论