260. 只出现一次的数字 III
给定一个整数数组
nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。你可以按 任意顺序 返回答案。进阶：你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？
示例 1：
输入：nums = [1,2,1,3,2,5] 输出：[3,5] 解释：[5, 3] 也是有效的答案。
示例 2：
输入：nums = [-1,0] 输出：[-1,0]
示例 3：
输入：nums = [0,1] 输出：[1,0]
提示：
2 <= nums.length <= 3 * 104
231<= nums[i] <= 231- 1
- 除两个只出现一次的整数外，
nums中的其他数字都出现两次
通过次数84,944提交次数115,132
法 1 异或
思路
先通过 对所有元素异或，得到两个不同数字的异或，再把这两个数字分开。
这两个数字肯定不一样，我们选择从右边数第一个1为标记，然后再用这个标记到原数组中找。
因为原数组中的值都是成对出现的，所以可以直接那这个标记和原数组中的值进行异或，这样最后剩下的就是答案
题解
class Solution: def singleNumber(self, nums: List[int]) -> List[int]: xor = 0 for num in nums: xor ^= num # 两个 res 最后一位不同的地方， # 因为异或是不同才为 1 ，所以找到 xor最后一个1即可 last_dif = xor & (-xor) # 两组分别计算 res1, res2 = 0, 0 for num in nums: if num & last_dif: res1 ^= num else: res2 ^= num return res1, res2