Hard

题目描述

列表的异或和是其所有元素的按位异或。如果列表只包含一个元素，那么其异或和将等于这个元素。

例如，[1,2,3,4] 的异或和等于 1 XOR 2 XOR 3 XOR 4 = 4，[3] 的异或和等于 3。

给你两个下标从 0 开始的数组 arr1 和 arr2，它们只包含非负整数。

考虑列表，其中包含每个 (i, j) 对的 arr1[i] AND arr2[j]（按位与）的结果，其中 0 <= i < arr1.length 且 0 <= j < arr2.length。

返回上述列表的异或和。

示例 1：

输入：arr1 = [1,2,3], arr2 = [6,5]
输出：0
解释：列表 = [1 AND 6, 1 AND 5, 2 AND 6, 2 AND 5, 3 AND 6, 3 AND 5] = [0,1,2,0,2,1]。
异或和 = 0 XOR 1 XOR 2 XOR 0 XOR 2 XOR 1 = 0。

示例 2：

输入：arr1 = [12], arr2 = [4]
输出：4
解释：列表 = [12 AND 4] = [4]。异或和 = 4。

约束条件：

  • 1 <= arr1.length, arr2.length <= 10^5
  • 0 <= arr1[i], arr2[j] <= 10^9

解题思路

这道题的关键在于利用位运算的分配律来优化计算。

暴力解法思路： 最直观的方法是计算所有 arr1[i] & arr2[j] 的结果，然后对这些结果求异或和。但这种方法的时间复杂度为 O(m×n)，在给定约束下会超时。

优化思路： 我们需要利用异或和按位与的数学性质：

  1. 异或运算的分配律：(a & b) ⊕ (a & c) = a & (b ⊕ c)
  2. 对于固定的 arr1[i]，所有与 arr2 中元素的按位与结果的异或和为：arr1[i] & (arr2[0] ⊕ arr2[1] ⊕ … ⊕ arr2[n-1])

因此，最终答案可以表示为：

  • 设 xor2 = arr2[0] ⊕ arr2[1] ⊕ … ⊕ arr2[n-1]
  • 答案 = (arr1[0] & xor2) ⊕ (arr1[1] & xor2) ⊕ … ⊕ (arr1[m-1] & xor2)
  • 进一步化简：答案 = (arr1[0] ⊕ arr1[1] ⊕ … ⊕ arr1[m-1]) & xor2

即：两个数组各自异或和的按位与结果。

这个优化将时间复杂度降低到 O(m + n)。

代码实现

class Solution {
public:
    int getXORSum(vector<int>& arr1, vector<int>& arr2) {
        int xor1 = 0, xor2 = 0;
        
        for (int num : arr1) {
            xor1 ^= num;
        }
        
        for (int num : arr2) {
            xor2 ^= num;
        }
        
        return xor1 & xor2;
    }
};

class Solution:
    def getXORSum(self, arr1: List[int], arr2: List[int]) -> int:
        xor1 = 0
        xor2 = 0
        
        for num in arr1:
            xor1 ^= num
        
        for num in arr2:
            xor2 ^= num
        
        return xor1 & xor2

public class Solution {
    public int GetXORSum(int[] arr1, int[] arr2) {
        int xor1 = 0, xor2 = 0;
        
        foreach (int num in arr1) {
            xor1 ^= num;
        }
        
        foreach (int num in arr2) {
            xor2 ^= num;
        }
        
        return xor1 & xor2;
    }
}

var getXORSum = function(arr1, arr2) {
    let xor1 = 0, xor2 = 0;
    
    for (let num of arr1) {
        xor1 ^= num;
    }
    
    for (let num of arr2) {
        xor2 ^= num;
    }
    
    return xor1 & xor2;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型暴力解法优化解法
时间复杂度O(m × n)O(m + n)
空间复杂度O(1)O(1)

其中 m = arr1.length，n = arr2.length。优化解法通过数学性质将复杂度从平方级降低到线性级。