leetcode
leetcode 1101 ~ 1150
四因数

四因数

难度:

标签:

题目描述

代码结果

运行时间: 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)

代码细节讲解

🦆
为什么首先检查数字的一个小于其平方根的因数,这种方法有什么特别的优势吗?
检查一个数字小于其平方根的因数是一种高效的因数查找方法。因为如果一个数n可以被另一个数d整除(即n = d * k),那么d和k中至少有一个必须小于或等于n的平方根。如果两者都大于n的平方根,那么d*k会大于n,这与假设矛盾。因此,只需要检查到平方根就可以了。这样减少了检查的范围,提高了算法效率。
🦆
题解中提到的两种具有四个因数的情况(p*q和p^3),这种分类是基于什么数学原理?能否详细解释一下?
这种分类基于因数的组成原理。对于形如p*q的数字,如果p和q是不同的质数,那么该数字具有的四个因数是1, p, q, pq。这是因为质数除了1和本身没有其他因数。对于形如p^3的数字,如果p是质数,那么它的四个因数是1, p, p^2, p^3。这两种情况都是在特定条件下因数恰好为四个的情况,分别对应两个不同质因数的乘积以及一个质数的三次方。
🦆
在函数`FourDivSum`中,如果数字是某个数的三次方(形如 p^3),为什么返回的是`sum([i ** j for j in range(4)])`?这里的计算逻辑是怎样的?
当数字是某个质数p的三次方时,即形如p^3,其因数是1, p, p^2, 和 p^3。在这里,`i`是这个质数p。因此,`sum([i ** j for j in range(4)])`的计算实际上是在计算1 (即p的0次方), p (即p的1次方), p^2 (即p的2次方), 和 p^3 (即p的3次方)的和。这样确保正确计算了所有的因数和。
🦆
当`i * i >= num`时,函数直接返回0,这个决策背后的逻辑是什么?是否意味着此时无法形成四个因数?
当`i * i >= num`时,意味着没有找到小于平方根的因数,因此num是质数或只有1和自身为因数的数字。在这种情况下,num不能有四个因数。返回0表示该数字不符合题目要求的具有四个不同因数的条件,因此在这种情况下不进行进一步的因数求和计算。

相关问题