跳转至

2425. 所有数对的异或和

题目描述

给你两个下标从 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 的长度。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
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;
}

评论