今日题目

https://leetcode.com/problems/bitwise-xor-of-all-pairings/description/

解题思路

根据题意，输出结果的公式为： $$ ans = \large{XOR}{\small i = 1}^{\small n} \large{XOR}{\small j = 1}^{\small m} nums1[i]\space xor \space nums2[j] $$ 其中 $\large{XOR}$ 表示从 $i$ 到 $n$ 依次进行 xor 运算。 $n$ 为 $nums1$ 的长度，$m$ 为 $nums2$ 的长度。

根据异或的交换律和结合律（详见此处），可以将公式变形为： $$ ans = \large{XOR}{\small i = 1}^{\small n} (nums1[i]^m) \space xor \space \large{XOR}{\small j = 1}^{\small m} (nums2[j]^n) $$ 再利用 $A\space xor A = 0$ 的性质，最终得到： $$ ans = \large{XOR}{\small i = 1}^{\small n} (nums1[i]^{m % 2}) \space xor \space \large{XOR}{\small j = 1}^{\small m} (nums2[j]^{n % 2}) $$

解题方法

遍历两个数组，按照上述公式计算结果。

复杂度分析

• 时间复杂度：$O(N + M)$，N 为 nums1 的长度，M 为 nums2 的长度。

• 空间复杂度：$O(1)$，无额外空间占用。

代码

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