【脑筋急转弯, 位运算】所有数对的异或和【力扣第 88 场双周赛】

题目

6213. 所有数对的异或和

---

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

解题

方法一：位运算

思路

首先我们需要了解异或运算的几个性质：

• 交换律：$p \oplus q = q \oplus p$
• 结合律：$p \oplus (q \oplus r) = (p \oplus q) \oplus r$
• 恒等律：$p \oplus 0 = p$
• 归零律：$p \oplus p = 0$
• 自反性：$p \oplus q \oplus q = p \oplus 0 = p$

知道了以上的性质，我们就会发现如果能统计出每个数在异或运算中出现的次数，就可以很快的算出结果。
如果一个数在异或运算中出现了偶数次，根据自反性，这个数就和结果没有任何关系，不需要考虑了。

根据题目我们知道，每个 num1 中的数字会在异或运算中出现 nums2.length 次，每个 nums2 中的数字会出现 nums1.length 次，这样以来我们只需要判断一个数组长度的奇偶就可以知道要不要把另一个数组加入到异或运算中去了。

参考：逻辑异或 - 维基百科

代码

class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int ans = 0;
        if ((nums1.length & 1) != 0) for (int num : nums2) ans ^= num;
        if ((nums2.length & 1) != 0) for (int num : nums1) ans ^= num;
        return ans;
    }
}

class Solution {
public:
    int xorAllNums(vector<int>& nums1, vector<int>& nums2) {
        int ans = 0;
        if (nums1.size() & 1) for (int num : nums2) ans ^= num;
        if (nums2.size() & 1) for (int num : nums1) ans ^= num;
        return ans;
    }
};

（我一开始写出来的解题代码）

class Solution {
    public int xorAllNums(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;
        int ans = 0;
        if ((m & 1) == 0 && (n & 1) == 0) return 0;
        else if ((m & 1) == 0) {
            for (int num : nums1) ans ^= num;
            return ans;
        } else if ((n & 1) == 0) {
            for (int num : nums2) ans ^= num;
            return ans;
        } else {
            for (int n1 : nums1) {
                for (int n2 : nums2) {
                    ans = ans ^ n1 ^ n2;
                }
            }
            return ans;
        }
    }
}