所有数对的异或和

难度: Medium

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

Submission

运行时间: 37 ms

内存: 34.1 MB

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        cnt = 0
        if m % 2:
            for num in nums2:
                cnt ^= num
        if n % 2:
            for num in nums1:
                cnt ^= num
        return cnt

Explain

此题解利用了异或运算的性质，主要是异或操作的交换律和结合律，以及任何数与自身异或的结果为0。首先，确定每个数在结果中出现的次数。若 `nums1` 或 `nums2` 的长度为奇数，则该数组中的每个元素将与对方数组中的每个元素配对，因此出现次数为对方数组的长度。如果两数组长度都是偶数，则每个元素参与异或的次数也是偶数，最终异或的结果为0。基于以上分析，只有当其中一个数组长度为奇数时，才需要计算其元素的异或总和。

时间复杂度: O(m + n)

空间复杂度: O(1)

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)  # 存储两数组的长度
        cnt = 0  # 初始化结果变量
        if m % 2:  # 如果 nums1 长度为奇数
            for num in nums2:  # 遍历 nums2 中的每个元素
                cnt ^= num  # 将 nums2 中的元素与 cnt 进行异或操作
        if n % 2:  # 如果 nums2 长度为奇数
            for num in nums1:  # 遍历 nums1 中的每个元素
                cnt ^= num  # 将 nums1 中的元素与 cnt 进行异或操作
        return cnt  # 返回最终的异或结果

Explore

当数组的长度为奇数时，其任何元素将与对方数组中的每个元素各匹配一次，因此参与异或的次数也为奇数次。由于异或运算中任何数与自身异或的结果为0，并且异或运算具有交换律和结合律，只有出现奇数次的数才可能在最终结果中不为0。因此，当其中一个数组长度为奇数时，其元素会影响最终的异或总和，需要计算它们的异或结果。

当两个数组的长度都是偶数时，每个数组中的元素与对方数组中的每个元素都将匹配一次，总共匹配次数是两个偶数的乘积，即偶数次。由于异或运算中任何数与自身异或结果是0，且出现偶数次的任何数在多次异或后结果也为0，因此最终的异或总和为0。

交换律允许我们改变异或操作的顺序而不影响结果，结合律允许我们改变操作的分组。这意味着无论元素的异或顺序如何，其最终结果都是相同的。这在算法中非常有用，因为我们可以随意顺序地从两个数组中选择元素进行异或，而不用担心顺序会影响最终结果。

当一个数组的长度为奇数时，该数组中的每个元素都会影响最终结果，因为它们每个都会与另一个数组中的每个元素匹配一次，即参与异或次数为奇数次。为了得到这种影响，只需要将另一个数组中的所有元素进行一次异或运算，这样就可以累计所有影响到结果的元素。如果两个数组都是奇数长度，则两个数组各自对最终结果的影响相互抵消，最终结果为0。