2425. 所有数对的异或和
2425. 所有数对的异或和
🟠 Medium 🔖 位运算
脑筋急转弯
数组
🔗 力扣
LeetCode
题目
You are given two 0-indexed arrays, nums1
and nums2
, consisting of non-negative integers. There exists another array, nums3
, which contains the bitwise XOR of all pairings of integers between nums1
and nums2
(every integer in nums1
is paired with every integer in nums2
exactly once).
Return the bitwise XOR of all integers in nums3
.
Example 1:
Input: nums1 = [2,1,3], nums2 = [10,2,5,0]
Output: 13
Explanation:
A possible nums3 array is [8,0,7,2,11,3,4,1,9,1,6,3].
The bitwise XOR of all these numbers is 13, so we return 13.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 0
Explanation:
All possible pairs of bitwise XORs are nums1[0] ^ nums2[0], nums1[0] ^ nums2[1], nums1[1] ^ nums2[0], and nums1[1] ^ nums2[1].
Thus, one possible nums3 array is [2,5,1,6].
2 ^ 5 ^ 1 ^ 6 = 0, so we return 0.
Constraints:
1 <= nums1.length, nums2.length <= 10^5
0 <= nums1[i], nums2[j] <= 10^9
题目大意
给你两个下标从 0 开始的数组 nums1
和 nums2
,两个数组都只包含非负整数。请你求出另外一个数组 nums3
,包含 nums1
和 nums2
中 所有数对 的异或和(nums1
中每个整数都跟 nums2
中每个整数 恰好 匹配一次)。
请你返回 nums3
中所有整数的 异或和 。
示例 1:
输入: nums1 = [2,1,3], nums2 = [10,2,5,0]
输出: 13
解释:
一个可能的 nums3 数组是 [8,0,7,2,11,3,4,1,9,1,6,3] 。
所有这些数字的异或和是 13 ,所以我们返回 13 。
示例 2:
输入: nums1 = [1,2], nums2 = [3,4]
输出: 0
解释:
所有数对异或和的结果分别为 nums1[0] ^ nums2[0] ,nums1[0] ^ nums2[1] ,nums1[1] ^ nums2[0] 和 nums1[1] ^ nums2[1] 。
所以,一个可能的 nums3 数组是 [2,5,1,6] 。
2 ^ 5 ^ 1 ^ 6 = 0 ,所以我们返回 0 。
提示:
1 <= nums1.length, nums2.length <= 10^5
0 <= nums1[i], nums2[j] <= 10^9
解题思路
统计
nums1
和nums2
中的数字被异或的次数:- 对于
nums1
中的每个数字,会被nums2
的所有数字异或len2
次。 - 对于
nums2
中的每个数字,会被nums1
的所有数字异或len1
次。
- 对于
遍历两个数组,对每个数字的总出现次数取模 2,判断是否对结果有贡献。
- 如果某个数字出现次数是偶数次,那么异或结果对总异或没有贡献。
- 如果某个数字出现次数是奇数次,那么它会对总异或产生贡献。
维护一个变量
res
,将所有有贡献的数字异或到res
中。
复杂度分析
- 时间复杂度:
O(n + m)
,其中n
和m
分别是nums1
和nums2
的长度,遍历nums1
和nums2
一次。 - 空间复杂度:
O(1)
,使用常量额外空间。
代码
/**
* @param {number[]} nums1
* @param {number[]} nums2
* @return {number}
*/
var xorAllNums = function (nums1, nums2) {
const len1 = nums1.length;
const len2 = nums2.length;
let res = 0;
if (len2 % 2 === 1) {
for (let num of nums1) {
res ^= num; // nums1 的每个数字参与 len2 次异或,当 len2 为奇数时,保留贡献
}
}
if (len1 % 2 === 1) {
for (let num of nums2) {
res ^= num; // nums2 的每个数字参与 len1 次异或,当 len1 为奇数时,保留贡献
}
}
return res;
};