跳至主要內容

2425. 所有数对的异或和


2425. 所有数对的异或和

🟠 Medium  🔖  位运算 脑筋急转弯 数组  🔗 力扣open in new window LeetCodeopen in new window

题目

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 开始的数组 nums1nums2 ,两个数组都只包含非负整数。请你求出另外一个数组 nums3 ,包含 nums1nums2所有数对 的异或和(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

解题思路

  1. 统计 nums1nums2 中的数字被异或的次数:

    • 对于 nums1 中的每个数字,会被 nums2 的所有数字异或 len2 次。
    • 对于 nums2 中的每个数字,会被 nums1 的所有数字异或 len1 次。
  2. 遍历两个数组,对每个数字的总出现次数取模 2,判断是否对结果有贡献。

    • 如果某个数字出现次数是偶数次,那么异或结果对总异或没有贡献。
    • 如果某个数字出现次数是奇数次,那么它会对总异或产生贡献。
  3. 维护一个变量 res,将所有有贡献的数字异或到 res 中。

复杂度分析

  • 时间复杂度O(n + m),其中 nm 分别是 nums1nums2 的长度,遍历 nums1nums2 一次。
  • 空间复杂度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;
};