leetcode
leetcode 1651 ~ 1700
找出所有子集的异或总和再求和

找出所有子集的异或总和再求和

难度:

标签:

题目描述

代码结果

运行时间: 19 ms, 内存: 16.0 MB


/*
题目思路:
1. 通过递归生成所有子集并计算异或总和。
2. 使用Stream API将所有子集的异或总和累加。
*/
import java.util.stream.IntStream;

public class Solution {
    public int subsetXORSum(int[] nums) {
        return IntStream.range(0, 1 << nums.length) // 1 << nums.length = 2^n
                .map(i -> IntStream.range(0, nums.length)
                        .filter(j -> (i & (1 << j)) != 0)
                        .map(j -> nums[j])
                        .reduce(0, (a, b) -> a ^ b))
                .sum();
    }
}

解释

方法:

该题解利用了组合数学中的一个性质:每个数组元素在所有子集中出现次数相同。具体地,对于数组中的每个元素,它在所有子集的异或运算中贡献的次数是2^(n-1)次,其中n是数组长度。首先使用reduce函数与or_操作计算出所有元素的异或运算结果。然后,通过左移操作 (<<),相当于将这个结果乘以2^(n-1),即每个元素贡献的次数,从而得到所有子集的异或总和之和。

时间复杂度:

O(n)

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在计算所有子集的异或总和时,每个元素都会出现2^(n-1)次?这个规律是如何得出的?
在一个包含n个元素的数组中,每个元素在生成的子集中出现次数是相同的。对于数组中的任意一个元素,选择其余n-1个元素生成子集时,该元素可以包含在内或不包含。这将产生2^(n-1)个可能的子集包含该元素,因此每个元素在所有子集中出现的次数是2^(n-1)次。这是因为每个子集是独立选择包含或不包含每个元素的,所以每个元素都等概率地出现在所有可能的子集中。
🦆
在题解中使用`reduce(or_, nums)`来计算异或总和的原因是什么?`or_`操作通常表示按位或,这里用来计算异或是否有误?
这里使用`reduce(or_, nums)`确实是有误的,因为`or_`表示的是按位或运算,而不是异或运算。正确的方法应该使用`xor`运算符来获取所有元素的异或总和。应该使用`reduce(xor, nums)`,其中`xor`是从`operator`模块导入的按位异或操作符。这样才能正确计算数组中所有元素的异或总和。
🦆
题解提到的左移操作`xor_all << (len(nums) - 1)`具体是如何计算每个元素在所有子集中出现次数的?这里的左移数为什么是`len(nums) - 1`而不是`len(nums)`?
左移操作`xor_all << (len(nums) - 1)`是用于将单个元素的异或结果扩展到其在所有子集中出现的次数。每个元素在所有子集中出现2^(n-1)次,因此将异或结果左移(len(nums) - 1)位,等价于将该结果乘以2^(n-1),从而反映了每个元素在所有可能子集中的总贡献。如果左移len(nums),那会是乘以2^n,这超过了实际的出现次数。
🦆
如果输入数组`nums`为空,这个方法能正确处理吗?按照题解的逻辑,是否需要在代码中添加特定的条件来处理这种情况?
如果输入数组为空,按照当前题解中的代码,`reduce(or_, nums)`会因为没有初始值而抛出异常。在这种情况下,正确的处理方法是检查数组是否为空,如果为空,则直接返回0因为没有任何子集,也就没有任何异或总和。可以在代码中加入一个条件检查来处理这种情况,例如在计算`xor_all`之前添加`if not nums: return 0`。

相关问题