1题目描述
给定一个整数数组 nums,其中恰好有两个元素只出现一次,其余所有元素均出现两次。找出只出现一次的那两个元素。如输入[1,2,3,2,4,1],输出[3,4]。
2解题
思路一:建立哈希表记录每个值出现的次数
依旧是最直接的方式,遍历每个值,建立字典记录出现次数,将出现次数为1的值建立一个列表,最后统一输出即可。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
countnum=dict()
for i in nums:
if i in countnum:
countnum[i]=countnum[i]+1
else:
countnum[i]=1
ans = list()
for e,v in countnum.items():
if v == 1:
ans.append(e)
return ans
思路二:集合操作
在LeetCode刷题DAY 5:只出现一次的数字和LeetCode刷题DAY 6:只出现一次的数字II中,是对两个集合求差集(如t-s则得到在t但不在s中的元素),这里我们要对集合求对称差集,即t^s,得到不同时出现在两个集合中的元素。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
nums.sort()
return list(set(nums[::2]) ^ set(nums[1::2]))
思路三:位运算
异或的特点是相同为0不同为1,因此第一轮对所有元素进行异或操作,得到两个不同元素的异或结果(mark=a^b)。通过计算mark&(-mark)保留mark中从右起第一个1,其余位置变为0(其中-mark=~mark+1)。这个右起第一个1,来自两个目标元素中的一个,因此找到相同位置为1的元素,进行异或操作找到第一个目标值,其他元素进行异或操作找到第二个目标值。
class Solution:
def singleNumber(self, nums: List[int]) -> int:
mark = 0
# 第一轮异或
for i in nums:
mark ^= i
y = mark & (-mark)
x1,x2 = 0,0
# 第二轮分组异或
for i in nums:
if i & y:
x1 = x1^i
else:
x2 = x2^i
return [x1,x2]