LeetCode刷题DAY 7：只出现一次的数字III
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]本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2020-05-05，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读