leetcode
leetcode 2101 ~ 2150
公因子的数目

公因子的数目

难度:

标签:

题目描述

代码结果

运行时间: 22 ms, 内存: 15.9 MB


/*
 * 思路:
 * 使用 Java Stream API 进行简化。
 * 可以使用 IntStream 来生成从 1 到 min(a, b) 的范围,
 * 然后过滤出能同时整除 a 和 b 的整数,
 * 最后计数这些整数的数量即可。
 */
import java.util.stream.IntStream;

public class CommonFactorsStream {
    public static int commonFactors(int a, int b) {
        int min = Math.min(a, b);
        return (int) IntStream.rangeClosed(1, min)
                              .filter(i -> a % i == 0 && b % i == 0)
                              .count();
    }

    public static void main(String[] args) {
        System.out.println(commonFactors(12, 6)); // 输出: 4
        System.out.println(commonFactors(25, 30)); // 输出: 2
    }
}

解释

方法:

该题解采用了暴力法来找到两个数a和b的所有公因子。首先,它遍历了所有从1到min(a, b)(含)的整数,因为任何大于a和b中的较小值的数不可能是它们的公因子。对于每一个这样的整数i,检查i是否同时是a和b的因子,即a和b都能被i整除。如果是,计数器ans增加1。遍历完成后,ans中的值就是a和b的公因子的总数。

时间复杂度:

O(min(a, b))

空间复杂度:

O(1)

代码细节讲解

🦆
在算法中,为何选择遍历到min(a, b)而不是max(a, b),能否详细解释这样选择的原因?
在寻找两个数a和b的公因子时,选择遍历到min(a, b)是因为超过min(a, b)的任何数都不可能成为两数的公因子。例如,如果一个数大于a和b中的任何一个,那么它不可能同时整除这两个数。因此,遍历到min(a, b)是合理的边界,可以有效减少不必要的计算,提高算法效率。
🦆
算法中使用了暴力法,是否存在更高效的算法来解决这个问题,例如基于最大公约数的方法?
确实存在基于最大公约数(Greatest Common Divisor, GCD)的更高效算法。首先计算a和b的GCD,然后找出这个GCD的所有因子。因为GCD定义为a和b的最大公因子,其所有的因子也必然是a和b的公因子。这种方法通常比暴力法更高效,因为计算GCD的时间复杂度较低(通常使用欧几里得算法),且GCD的值通常小于min(a, b),因此需要检验的因子数也较少。
🦆
在算法实现中,ans变量用于计数公因子,这种计数方式是否有可能在某些情况下导致重复计数?
在这个算法实现中,ans变量用于计数公因子,这种方法不会导致重复计数。因为每个i只会在循环中被检查一次,若i同时是a和b的因子,则ans增加1。由于每个i都是独立考虑的,不存在重复检查或增加同一个因子的情况。
🦆
在实际代码实现过程中,是否考虑了输入的异常情况,例如a或b为非常小或非常大的边界值?
题解中的代码实现简单,直接遍历从1到min(a, b)的所有整数,没有特别处理输入的边界值。但由于Python的int类型在处理大整数时可以自动扩展大小,因此在处理非常大的数时通常不会有问题,除非数值超出了内存限制。对于非常小的数(如0或负数),该算法没有显式错误处理,可能需要在实际应用中增加输入验证来确保数据的有效性和合理性。

相关问题