Medium

题目描述

给你两个下标从 0 开始的数组 nums1 和 nums2，两个数组都由非负整数组成。请你求出另一个数组 nums3，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^5
  • 0 <= nums1[i], nums2[j] <= 10^9

解题思路

这道题的关键在于理解异或运算的性质：a ^ a = 0，a ^ 0 = a。

核心思路： 不需要真正构造出所有的数对，而是分析每个数字在最终结果中的贡献次数。

如果 nums1 长度为 m，nums2 长度为 n，那么：

  • nums1 中的每个数字会与 nums2 中所有数字配对，因此每个 nums1[i] 在结果中出现 n 次
  • nums2 中的每个数字会与 nums1 中所有数字配对，因此每个 nums2[j] 在结果中出现 m 次

由于异或的性质，如果一个数字出现偶数次，对结果无贡献；如果出现奇数次，则该数字会保留在最终结果中。

因此：

  • 如果 n 是奇数，那么 nums1 中所有数字的异或值会保留
  • 如果 m 是奇数，那么 nums2 中所有数字的异或值会保留
  • 最终结果就是这两部分的异或

这种方法的时间复杂度是 O(m+n)，空间复杂度是 O(1)，远优于暴力的 O(mn) 解法。

代码实现

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size(), n = nums2.size();
        int result = 0;
        
        // 如果 n 是奇数，nums1 中每个数字会被保留
        if (n & 1) {
            for (int num : nums1) {
                result ^= num;
            }
        }
        
        // 如果 m 是奇数，nums2 中每个数字会被保留
        if (m & 1) {
            for (int num : nums2) {
                result ^= num;
            }
        }
        
        return result;
    }
};

class Solution:
    def xorAllNums(self, nums1: List[int], nums2: List[int]) -> int:
        m, n = len(nums1), len(nums2)
        result = 0
        
        # 如果 n 是奇数，nums1 中每个数字会被保留
        if n & 1:
            for num in nums1:
                result ^= num
        
        # 如果 m 是奇数，nums2 中每个数字会被保留
        if m & 1:
            for num in nums2:
                result ^= num
        
        return result

public class Solution {
    public int XorAllNums(int[] nums1, int[] nums2) {
        int m = nums1.Length, n = nums2.Length;
        int result = 0;
        
        // 如果 n 是奇数，nums1 中每个数字会被保留
        if ((n & 1) == 1) {
            foreach (int num in nums1) {
                result ^= num;
            }
        }
        
        // 如果 m 是奇数，nums2 中每个数字会被保留
        if ((m & 1) == 1) {
            foreach (int num in nums2) {
                result ^= num;
            }
        }
        
        return result;
    }
}

var xorAllNums = function(nums1, nums2) {
    const m = nums1.length, n = nums2.length;
    let result = 0;
    
    // 如果 n 是奇数，nums1 中每个数字会被保留
    if (n & 1) {
        for (const num of nums1) {
            result ^= num;
        }
    }
    
    // 如果 m 是奇数，nums2 中每个数字会被保留
    if (m & 1) {
        for (const num of nums2) {
            result ^= num;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度
时间复杂度O(m + n)
空间复杂度O(1)

其中 m 和 n 分别是 nums1 和 nums2 的长度。