[面试题] 最小因式分解算法详解：贪心策略解决Python面试编码题

违约金条款是技术求职中的一个重要环节，每家公司标准各异，其核心矛盾在于签约与履约之间的心理博弈。结合网络上的普遍讨论，笔者认为，职场规则的本质是契约精神，合理的违约条款对双方都是一种约束与保障，确保招聘与求职市场的稳定运行。

而深入技术层面，守诺与遵守规则的精神，同样体现在我们解决每一个具体的编码问题中。下面，我们将通过一道名为“最小因式分解”的经典算法题，来探讨如何运用清晰的逻辑和高效的策略来“履约”——即给出问题的最优解。

面试题解析：最小因式分解

问题描述：给定一个正整数 n，你需要将其分解为若干个在 2 到 9 之间的整数因子（可以重复）。然后，将这些因子作为数字位，组合成一个新的整数。目标是使这个新整数尽可能小。如果无法进行这样的分解，则返回 -1。

示例说明：

• 当 n = 48，可以分解为 6 * 8，组合成整数 68；也可以分解为 2 * 2 * 2 * 2 * 3，组合成 22223。显然 68 更小。
• 当 n = 11，它是一个大于9的质数，无法用2~9之间的数分解，因此返回 -1。

算法核心：贪心策略

解题的关键在于一种朴素的贪心思想：尽可能使用较大的因子（9~2）进行分解，以减少最终组合数字的位数。

算法步骤：

1. 特判：如果 n 本身就在 0~9 之间（根据题意通常 n>1），它自身就是答案。
2. 逆向遍历分解：从数字 9 到 2 进行遍历。
   • 只要当前数字 d 能整除 n，就将其记录到因子列表 factors 中，并将 n 除以 d。
   • 循环执行，直到 d 不能再整除 n，再尝试下一个更小的数字。
3. 结果检查：遍历结束后，如果 n 的值大于 1，说明剩余了一个大于 9 的质因数，无法分解，返回 -1。
4. 构造最小数字：由于分解时是从大到小获取因子，因此 factors 列表是降序的（例如 [9, 4]）。要组成最小的整数，需要将因子按升序排列（[4, 9]），然后依次组合成数字 49。

贪心正确性直观理解：用一个大因子（如8）代替多个小因子（如222），能直接减少数字的位数。位数减少带来的收益，远大于因某一位数字增大可能带来的损失。例如，68（两位）一定小于 22223（五位）。

Python代码实现

以下是根据上述思路用Python写出的清晰解法：

def smallest_factorization(n: int) -> int:
    """
    将正整数 n 分解为若干 2~9 的因子，并将这些因子组合成最小的整数。
    若无解则返回 -1。
    """
    # 特殊情况处理
    if n >= 0 and n < 10:
        return n

    factors = []
    # 贪心：从大到小尝试因子
    for d in range(9, 1, -1):
        while n % d == 0:
            factors.append(d)
            n //= d

    # 存在无法分解的大质因子
    if n != 1:
        return -1

    # 将因子从小到大排序以组成最小数字
    factors.sort()
    # 组合数字并检查整数范围（针对部分题目要求）
    result = 0
    for num in factors:
        result = result * 10 + num
        # 若题目要求结果在32位有符号整数范围内，可添加此检查
        if result > 2**31 - 1:
            return -1
    return result

if __name__ == "__main__":
    test_cases = [15, 48, 11, 36, 100]
    for x in test_cases:
        print(f"{x} => {smallest_factorization(x)}")

输出示例：

• 15 => 35 (3 * 5)
• 48 => 68 (6 * 8)
• 11 => -1
• 36 => 49 (4 * 9)
• 100 => 455 (4 5 5)

复杂度分析

• 时间复杂度：O(log n)。外层循环仅遍历 9~2 这8个常数，内层while循环每次至少将 n 除以 2，因此循环次数与 n 的质因数个数（即对数级别）相关。
• 空间复杂度：O(log n)。用于存储因子列表 factors。

总结

这道“最小因式分解”题是贪心算法的一个典型应用。它考察了应聘者对问题本质的洞察力（位数优先），以及将思路转化为简洁代码的能力。理解并掌握这种“从大到小”尝试因子的贪心策略，是快速解决此类问题的关键。该smallest_factorization函数也体现了算法设计中处理边界条件（如无解情况和整数溢出）的完备性思考。