AlgoNote 算法通关手册：LeetCode 0625 最小因式分解（贪心 + 因数分解）完整题解

• 教程
• 文档
• 知识库

给定正整数num，要求构造一个最小的正整数x，使x每一位数字相乘恰好等于num——这是 LeetCode 第 625 题「最小因式分解」的核心问题。本篇基于《算法通关手册》题解库中的 minimum-factorization.md 展开，结合仓库中 贪心算法章节 的理论框架，完整讲解「贪心 + 因数分解」的推导过程、边界处理与复杂度分析。读完本篇，你将掌握一类「数位乘积还原」问题的通用贪心建模方法，并能在 32 位整数溢出限制下正确实现答案。

题目信息

• 题目编号：0625. 最小因式分解（Minimum Factorization）
• 标签：贪心、数学
• 难度：中等
• 题解在题库中的位置：docs/solutions/0600-0699/minimum-factorization.md，并收录于 完整题解列表 与 贪心算法题目分类

题目大意

描述：给定一个正整数num。

要求：找出最小的正整数x，使得x的所有数位相乘恰好等于num。这里的「数位相乘」指将x的十进制每一位数字（只能是 0~9 的整数）连乘。

说明：

• 数据范围：$1 \le num \le 2^{31} - 1$。
• 如果不存在这样的结果，或者结果不是 32 位有符号整数，返回0。

示例：

• 示例 1：

输入：num = 48 输出：68

解释：$6 \times 8 = 48$，且不存在比 68 更小的满足条件的正整数。例如 $2 \times 3 \times 8 = 48$ 对应 238，$2 \times 4 \times 6 = 48$ 对应 246，均大于 68。

• 示例 2：

输入：num = 15 输出：35

解释：$3 \times 5 = 15$，比 15 本身更小（num=15时若直接返回 15，其数位乘积是 $1 \times 5 = 5$，不满足要求）。

反例直观感受：

• num = 7：答案就是 7（$7 = 7$）。
• num = 22：22 含有大于 9 的质因子 11，无法拆成若干 2~9 的数字相乘，返回0。

解题思路：贪心 + 因数分解

思路 1：算法描述

问题的数学本质是：把num分解成若干个**一位数字（2~9）**的乘积，并把选出的数字按某种顺序拼接成整数，使拼接结果最小。

核心思路（两条贪心准则）：

1. 位数尽可能少：同样数值条件下，位数越少的整数越小（先比位数，再比高位）。因此应尽量用大的数字因子（如 9、8）去分解num，减少结果的位数。
2. 数字从小到大排列：在位数相同的前提下，把较小的数字放在高位，构成的整数更小（类似字典序）。因此选定数字后要升序拼接。

这两条准则正是仓库 贪心算法章节 中「贪心选择性质 + 最优子结构」的直接应用：每一步都选取当前能取到的最大一位因子，剩下的商继续作为子问题递归分解，局部最优累积为全局最优。

算法步骤：

1. 特判：如果num < 10，直接返回num。此时一位数x = num的数位乘积就是它本身，且无法构造出更小的结果。
2. 从 9 到 2 依次尝试分解num：
   • 如果num能被i整除，将i加入结果列表；
   • 用num //= i更新num，继续尝试整除i（同一因子可能被多次使用，对应数字重复出现）。
3. 检查剩余：如果最终num > 1，说明num中存在大于 9 的质因子，无法用 2~9 的一位数字完全表示，返回0。
4. 排序拼接：将结果列表从小到大排序（贪心：让结果最小），依次result = result * 10 + digit拼成整数。
5. 溢出检查：如果result > 2**31 - 1，说明结果超出 32 位有符号整数范围，返回0；否则返回result。

思路 1：代码

class Solution: def smallestFactorization(self, num: int) -> int: # 特殊情况：num < 10 时，一位数本身即为答案 if num < 10: return num # 从 9 到 2 依次分解 num，优先取最大的一位因子 digits = [] for i in range(9, 1, -1): while num % i == 0: digits.append(i) num //= i # 如果 num > 1，说明存在大于 9 的质因子，无法分解 if num > 1: return 0 # 将数字从小到大排列（贪心：让结果最小） digits.sort() # 将数字列表转换为整数 result = 0 for digit in digits: result = result * 10 + digit # 检查是否超过 32 位有符号整数范围 if result > 2**31 - 1: return 0 return result

思路 1：复杂度分析

• 时间复杂度：$O(\log num)$。内层while每次循环至少把num缩小 2 倍（num //= i，其中 $i \ge 2$），因此总迭代次数为 $O(\log num)$ 级别；digits.sort()对不超过 $\log_2 num$ 个数字排序，同样为 $O(\log num \cdot \log\log num)$ 量级，整体仍是 $O(\log num)$。
• 空间复杂度：$O(\log num)$，需要存储分解后得到的数字列表，最多约 $\log_2 num$ 个元素。

贪心正确性剖析

为什么「先取大因子」是最优的？

设 $num$ 的全部质因子分解为 $p_1^{e_1} p_2^{e_2} \cdots$。若某个质因子 $p > 9$，则它无法单独作为一位数字出现，也无法与其他质因子合并成一位数字（10~99 的合数都可以继续拆成一位数字），因此num必然包含一个质因子大于 9 时不可分解——对应代码中if num > 1: return 0的判定。

当所有质因子都在 2~9 范围内时，问题的关键是合并策略：例如 $2 \times 2 \times 2 \times 3 = 24$，如果直接保留为 2、2、2、3，拼接结果 2223；但如果合并成 8 和 3，拼接结果 38 更小。可以看出：用大数字因子合并，能同时减少位数并让高位更小。

• 减少位数：$2 \times 2 \times 2 = 8$，三位变一位；
• 高位更小：合并后数字整体更小，例如 $2 \times 2 \times 3 = 12$ 应优先写成 26（$2 \times 6 = 12$）而不是 223。

这就是从 9 到 2 逆序贪心分解的原因：9吸收了三个3，8吸收了三个2，6吸收了 2 和 3……从大到小贪心，可保证每个可合并的数字都被最大化合并，从而位数最少。

为什么「数字升序排列」得到最小整数？

位数相同的两个正整数，比较大小等价于从高位到低位逐位比较（字典序）。把数字因子按升序排列后，最高位最小，依次类推，因此得到的整数是这些数字所有排列中最小者。这一点与仓库贪心章节「经典例题：分发饼干」中「先排序再贪心」的思想一脉相承。

边界情况汇总

值得注意：num < 10时答案恰为num本身（例如num = 8时x = 8），这是题目定义下唯一且最小的解；num = 1时同理返回 1。

从仓库源码看同类题与延伸

《算法通关手册》将本题归类于「贪心、数学」标签，与仓库中其他贪心题目（如 0455 分发饼干、0860 柠檬水找零、0435 无重叠区间）同属一类「局部最优推全局最优」的建模套路：

• 问题转化：把「构造最小整数」转化为「分解 + 排序拼接」两个独立子问题；
• 贪心策略制定：每次取最大可行的一位因子（先保位数最少），再升序拼接（再保高位最小）；
• 最优子结构利用：每次整除后的商仍遵循相同结构递归处理。

若想系统补全贪心理论基础（贪心选择性质、最优子结构、正确性证明的交换论证法），可直接阅读仓库 07_05 贪心算法 章节；刷题完成后，可回到 贪心算法题目分类列表 继续巩固同类题目。

小结

LeetCode 0625「最小因式分解」是一道将「数位乘积还原」与贪心思想结合的经典中等题。核心解法只有三条：特判一位数 → 从 9 到 2 贪心分解 → 升序拼接并做 32 位溢出检查。掌握这道题的分解合并逻辑，不仅能够秒杀本题，还能迁移到「将一个数拆成若干合法数字因子使拼接结果最小/最大」一类面试题中，是贪心 + 数论交叉考点的必刷样例。

• 教程
• 文档
• 知识库