最小因式分解
难度:
标签:
题目描述
代码结果
运行时间: 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?
▷🦆
代码中如果`num`最终不为1,而是一个大于1的素数,为什么返回0?这样处理的原因是什么?
▷🦆
在构建结果时,直接通过`ans = mul * i + ans`累加,这种处理方式是否有可能导致数字溢出?如果是,应该如何避免?
▷🦆
算法实现中使用了`mul`变量以10的整数次幂形式来控制因子的位置,这种方法是否有可能在某些极端情况下导致结果错误或计算上的不准确?
▷