class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
}
};
100309. 求出出现两次数字的 XOR 值
给你一个数组 nums ，数组中的数字 要么 出现一次，要么 出现两次。
请你返回数组中所有出现两次数字的按位 XOR 值，如果没有数字出现过两次，返回 0 。
示例 1：
输入：nums = [1,2,1,3]
输出：1
解释：
nums 中唯一出现过两次的数字是 1 。
示例 2：
输入：nums = [1,2,3]
输出：0
解释：
nums 中没有数字出现两次。
示例 3：
输入：nums = [1,2,2,1]
输出：3
解释：
数字 1 和 2 出现过两次。1 XOR 2 == 3 。
提示：
1 <= nums.length <= 501 <= nums[i] <= 50nums 中每个数字要么出现过一次，要么出现过两次。原站题解
javascript 解法, 执行用时: 76 ms, 内存消耗: 51.9 MB, 提交时间: 2024-10-12 09:17:02
/**
* @param {number[]} nums
* @return {number}
*/
var duplicateNumbersXOR = function(nums) {
let ans = 0;
// JS 的位运算会强转成 32 位整数，需要用 BigInt 处理
let vis = 0n;
for (const x of nums) {
if (vis >> BigInt(x) & 1n) {
ans ^= x;
} else {
vis |= 1n << BigInt(x);
}
}
return ans;
};
rust 解法, 执行用时: 0 ms, 内存消耗: 2.1 MB, 提交时间: 2024-10-12 09:16:43
impl Solution {
pub fn duplicate_numbers_xor(nums: Vec<i32>) -> i32 {
let mut ans = 0;
let mut vis = 0i64;
for x in nums {
if (vis >> x & 1) > 0 {
ans ^= x;
} else {
vis |= 1 << x;
}
}
ans
}
}
java 解法, 执行用时: 0 ms, 内存消耗: 41.7 MB, 提交时间: 2024-05-26 18:52:18
class Solution {
public int duplicateNumbersXOR(int[] nums) {
int ans = 0;
long vis = 0;
for (int x : nums) {
if ((vis >> x & 1) > 0) {
ans ^= x;
} else {
vis |= 1L << x;
}
}
return ans;
}
}
cpp 解法, 执行用时: 3 ms, 内存消耗: 25.3 MB, 提交时间: 2024-05-26 18:52:05
class Solution {
public:
int duplicateNumbersXOR(vector<int>& nums) {
int ans = 0;
long long vis = 0;
for (int x : nums) {
if (vis >> x & 1) {
ans ^= x;
} else {
vis |= 1LL << x;
}
}
return ans;
}
};
golang 解法, 执行用时: 5 ms, 内存消耗: 2.5 MB, 提交时间: 2024-05-26 18:51:07
func duplicateNumbersXOR(nums []int) (ans int) {
vis := 0
for _, x := range nums {
if vis>>x&1 > 0 {
ans ^= x
} else {
vis |= 1 << x
}
}
return
}
python3 解法, 执行用时: 34 ms, 内存消耗: 16.5 MB, 提交时间: 2024-05-26 18:50:44
'''
遍历 nums，同时用一个 vis 集合记录遇到的数字。
设 x=nums[i]。
如果 x 不在 vis 中，说明是第一次遇到，加入 vis。
如果 x 在 vis 中，说明是第二次遇到（注意每个数至多出现两次），加入答案（异或）。
'''
class Solution:
def duplicateNumbersXOR(self, nums: List[int]) -> int:
ans = vis = 0
for x in nums:
if vis >> x & 1:
ans ^= x
else:
vis |= 1 << x
return ans