leetcode
leetcode 551 ~ 600
最小因式分解

最小因式分解

难度:

标签:

题目描述

代码结果

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


/*
 * 思路: 使用Java Stream的方式,我们依然可以从9到2尝试,将给定的数不断除以这些因子。
 * 如果最终得到的数字只包含因子范围内的数字,则说明分解成功,否则分解失败。
 */
 
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class Solution {
    public int smallestFactorization(int a) {
        if (a < 2) return a;
        String result = IntStream.rangeClosed(2, 9)
                                  .mapToObj(i -> new int[]{i})
                                  .flatMapToInt(arr -> IntStream.iterate(arr[0], i -> i * arr[0]).limit((int) (Math.log(a) / Math.log(arr[0]))))
                                  .filter(i -> a % i == 0)
                                  .mapToObj(String::valueOf)
                                  .sorted((x, y) -> Integer.compare(Integer.parseInt(y), Integer.parseInt(x)))
                                  .collect(Collectors.joining());
        try {
            return Integer.parseInt(result);
        } catch (NumberFormatException e) {
            return 0;
        }
    }
}
 

解释

方法:

这个题解的思路是对给定的数字 num 进行因式分解,从 9 到 2 依次枚举因子 i,将 num 中所有因子 i 提取出来,构建最小的因式分解结果。具体做法是,从高到低枚举因子 i,若 num 可以被 i 整除,则将 i 添加到结果的个位,同时将 num 除以 i。在添加因子 i 时,使用 mul 记录当前因子在结果中的位置,每添加一个因子,mul 就乘以 10,保证因子按照从小到大的顺序构建结果。最终,如果 num 被完全分解且结果不超过 2^31-1,则返回构建的最小因式分解结果,否则返回 0。

时间复杂度:

O(log(num))

空间复杂度:

O(1)

代码细节讲解

🦆
为什么在因式分解时选择因子从9到2逆序枚举,而不是正序从2到9?
在因式分解时选择因子从9到2逆序枚举的主要目的是构建最小的因式分解结果。从大到小的顺序可以确保较大的因数尽可能靠右,从而使得构成的数字尽可能小。如果从2到9正序枚举,较小的因子会被优先使用,导致最高位可能是较小的数字,最终构成的数字会更大。
🦆
代码中如果`num`最终不为1,而是一个大于1的素数,为什么返回0?这样处理的原因是什么?
如果在因式分解过程中`num`最终不为1,而是一个大于1的素数,这意味着`num`无法完全通过2到9的因子进行分解。在此情况下返回0是为了表示无法通过题目要求的因子完全分解`num`。这种处理确保了只有那些可以完全分解的数才返回有效的因式分解结果,保证了结果的正确性和有效性。
🦆
在构建结果时,直接通过`ans = mul * i + ans`累加,这种处理方式是否有可能导致数字溢出?如果是,应该如何避免?
直接通过`ans = mul * i + ans`累加的确有可能导致数字溢出,特别是当`ans`逐渐变大,接近32位整数的界限时。为了避免溢出,可以在每次更新`ans`之前检查是否会超过`2**31 - 1`。如果即将超过,应立即停止进一步的计算并返回0,这样可以防止溢出并返回无效的结果。
🦆
算法实现中使用了`mul`变量以10的整数次幂形式来控制因子的位置,这种方法是否有可能在某些极端情况下导致结果错误或计算上的不准确?
使用`mul`变量以10的整数次幂形式来控制因子的位置是一种常用的技术,用于确保数字的每一位都正确地反映了其因数。虽然这种方法在大多数情况下是有效的,但在极端情况下(如因式分解结果接近32位整数的上限时),可能会导致乘法操作中的溢出。在这种情况下,应该在每次更新`ans`和`mul`时检查它们的值是否会导致溢出,以确保计算的准确性和结果的有效性。

相关问题