leetcode
leetcode 2101 ~ 2150
所有数对的异或和

所有数对的异或和

难度:

标签:

题目描述

代码结果

运行时间: 37 ms, 内存: 34.1 MB


/*
题目思路:
1. 使用Java Stream API来计算nums1和nums2中每个数对的异或值。
2. 将所有异或值收集到一个列表中。
3. 使用reduce方法来计算列表中所有数的异或和。
*/

import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;

public class Solution {
    public int xorAll(int[] nums1, int[] nums2) {
        // 计算所有数对的异或值,并收集到一个列表中
        List<Integer> xorList = Arrays.stream(nums1)
            .boxed()
            .flatMap(num1 -> Arrays.stream(nums2).mapToObj(num2 -> num1 ^ num2))
            .collect(Collectors.toList());
        // 计算列表中所有数的异或和
        return xorList.stream().reduce(0, (a, b) -> a ^ b);
    }
}

解释

方法:

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

时间复杂度:

O(m + n)

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,为何只有当数组长度为奇数时,才需要计算其元素的异或总和?
当数组的长度为奇数时,其任何元素将与对方数组中的每个元素各匹配一次,因此参与异或的次数也为奇数次。由于异或运算中任何数与自身异或的结果为0,并且异或运算具有交换律和结合律,只有出现奇数次的数才可能在最终结果中不为0。因此,当其中一个数组长度为奇数时,其元素会影响最终的异或总和,需要计算它们的异或结果。
🦆
如何理解题解中提到的‘如果两数组长度都是偶数,则每个元素参与异或的次数也是偶数,最终异或的结果为0’?
当两个数组的长度都是偶数时,每个数组中的元素与对方数组中的每个元素都将匹配一次,总共匹配次数是两个偶数的乘积,即偶数次。由于异或运算中任何数与自身异或结果是0,且出现偶数次的任何数在多次异或后结果也为0,因此最终的异或总和为0。
🦆
题解提到使用了异或运算的交换律和结合律,可以具体解释这两个律是如何在这个问题中应用的吗?
交换律允许我们改变异或操作的顺序而不影响结果,结合律允许我们改变操作的分组。这意味着无论元素的异或顺序如何,其最终结果都是相同的。这在算法中非常有用,因为我们可以随意顺序地从两个数组中选择元素进行异或,而不用担心顺序会影响最终结果。
🦆
为什么在算法实现中,当一个数组的长度为奇数时,只遍历另一个数组的元素进行异或操作?
当一个数组的长度为奇数时,该数组中的每个元素都会影响最终结果,因为它们每个都会与另一个数组中的每个元素匹配一次,即参与异或次数为奇数次。为了得到这种影响,只需要将另一个数组中的所有元素进行一次异或运算,这样就可以累计所有影响到结果的元素。如果两个数组都是奇数长度,则两个数组各自对最终结果的影响相互抵消,最终结果为0。

相关问题