找出所有子集的异或总和再求和
难度:
标签:
题目描述
代码结果
运行时间: 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)次?这个规律是如何得出的?
▷🦆
在题解中使用`reduce(or_, nums)`来计算异或总和的原因是什么?`or_`操作通常表示按位或,这里用来计算异或是否有误?
▷🦆
题解提到的左移操作`xor_all << (len(nums) - 1)`具体是如何计算每个元素在所有子集中出现次数的?这里的左移数为什么是`len(nums) - 1`而不是`len(nums)`?
▷🦆
如果输入数组`nums`为空,这个方法能正确处理吗?按照题解的逻辑,是否需要在代码中添加特定的条件来处理这种情况?
▷