Question

2425. 所有数对的异或和

English Version

题目描述

给你两个下标从 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 <= 105
• 0 <= nums1[i], nums2[j] <= 109

解法

方法一：脑筋急转弯 + 位运算

由于数组的每个元素都会与另一个数组的每个元素进行异或，我们知道，同一个数异或两次，结果不变，即 $a \oplus a = 0$。因此，我们只需要统计数组的长度，就能知道每个元素与另一个数组的每个元素进行异或的次数。

如果 nums2 数组长度为奇数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了奇数次异或，因此 nums1 数组的最终异或结果即为 nums1 数组的所有元素异或的结果。如果为偶数，那么相当于 nums1 中每个元素都与 nums2 中的每个元素进行了偶数次异或，因此 nums1 数组的最终异或结果为 0。

同理，我们可以得知 nums2 数组的最终异或结果。

最终把两个异或结果再异或一次，即可得到最终结果。

时间复杂度 $O(m+n)$。其中 $m$ 和 $n$ 分别为数组 nums1 和 nums2 的长度。

class Solution:
  def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
    ans = 0
    if len(nums2) & 1:
      for v in nums1:
        ans ^= v
    if len(nums1) & 1:
      for v in nums2:
        ans ^= v
    return ans

class Solution {
  public int xorAllNums(int[] nums1, int[] nums2) {
    int ans = 0;
    if (nums2.length % 2 == 1) {
      for (int v : nums1) {
        ans ^= v;
      }
    }
    if (nums1.length % 2 == 1) {
      for (int v : nums2) {
        ans ^= v;
      }
    }
    return ans;
  }
}

class Solution {
public:
  int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
    int ans = 0;
    if (nums2.size() % 2 == 1) {
      for (int v : nums1) {
        ans ^= v;
      }
    }
    if (nums1.size() % 2 == 1) {
      for (int v : nums2) {
        ans ^= v;
      }
    }
    return ans;
  }
};

func xorAllNums(nums1 []int, nums2 []int) int {
  ans := 0
  if len(nums2)%2 == 1 {
    for _, v := range nums1 {
      ans ^= v
    }
  }
  if len(nums1)%2 == 1 {
    for _, v := range nums2 {
      ans ^= v
    }
  }
  return ans
}

function xorAllNums(nums1: number[], nums2: number[]): number {
  let ans = 0;
  if (nums2.length % 2 != 0) {
    ans ^= nums1.reduce((a, c) => a ^ c, 0);
  }
  if (nums1.length % 2 != 0) {
    ans ^= nums2.reduce((a, c) => a ^ c, 0);
  }
  return ans;
}