四因数
难度:
标签:
题目描述
代码结果
运行时间: 152 ms, 内存: 18.0 MB
/*
* 题目思路:
* 使用Java Stream来实现同样的逻辑。
* 对于每个数字,找到它的因数,并使用流处理来计算因数的和。
*/
import java.util.stream.IntStream;
public class FourDivisorsStream {
public int sumFourDivisors(int[] nums) {
return IntStream.of(nums).map(this::sumOfFourDivisors).sum();
}
private int sumOfFourDivisors(int num) {
int[] divisors = new int[4];
int count = 0, sum = 0;
for (int i = 1; i * i <= num; i++) {
if (num % i == 0) {
if (count < 4) divisors[count++] = i;
if (i != num / i && count < 4) divisors[count++] = num / i;
}
}
if (count == 4) sum = IntStream.of(divisors).sum();
return sum;
}
}
解释
方法:
这个题解的核心思路是通过遍历数组中的每个数字,并检查每个数字具有四个因数的情况。对每个数字,它首先尝试找到第一个小于其平方根的因数。如果找到这样的因数,它会尝试确定这个因数和剩余的商是否可以形成四个因数的组合。数学上,一个数字有四个因数的情况通常是它由两个不同的质因数组成(形如 p*q),或它是某个质数的三次方(形如 p^3)。对于每个数字的因数检查,如果符合四因数的条件,则计算这四个因数的和。为了避免重复计算,使用一个哈希表来存储已经计算过的数字及其因数之和。
时间复杂度:
O(m*sqrt(n))
空间复杂度:
O(m)
代码细节讲解
🦆
为什么首先检查数字的一个小于其平方根的因数,这种方法有什么特别的优势吗?
▷🦆
题解中提到的两种具有四个因数的情况(p*q和p^3),这种分类是基于什么数学原理?能否详细解释一下?
▷🦆
在函数`FourDivSum`中,如果数字是某个数的三次方(形如 p^3),为什么返回的是`sum([i ** j for j in range(4)])`?这里的计算逻辑是怎样的?
▷🦆
当`i * i >= num`时,函数直接返回0,这个决策背后的逻辑是什么?是否意味着此时无法形成四个因数?
▷