教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载给定正整数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 本身更小num15时若直接返回 15其数位乘积是 $1 \times 5 5$不满足要求。反例直观感受num 7答案就是 7$7 7$。num 2222 含有大于 9 的质因子 11无法拆成若干 2~9 的数字相乘返回0。解题思路贪心 因数分解思路 1算法描述问题的数学本质是把num分解成若干个**一位数字2~9**的乘积并把选出的数字按某种顺序拼接成整数使拼接结果最小。核心思路两条贪心准则位数尽可能少同样数值条件下位数越少的整数越小先比位数再比高位。因此应尽量用大的数字因子如 9、8去分解num减少结果的位数。数字从小到大排列在位数相同的前提下把较小的数字放在高位构成的整数更小类似字典序。因此选定数字后要升序拼接。这两条准则正是仓库 贪心算法章节 中「贪心选择性质 最优子结构」的直接应用每一步都选取当前能取到的最大一位因子剩下的商继续作为子问题递归分解局部最优累积为全局最优。算法步骤特判如果num 10直接返回num。此时一位数x num的数位乘积就是它本身且无法构造出更小的结果。从 9 到 2 依次尝试分解num如果num能被i整除将i加入结果列表用num // i更新num继续尝试整除i同一因子可能被多次使用对应数字重复出现。检查剩余如果最终num 1说明num中存在大于 9 的质因子无法用 2~9 的一位数字完全表示返回0。排序拼接将结果列表从小到大排序贪心让结果最小依次result result * 10 digit拼成整数。溢出检查如果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吸收了三个38吸收了三个26吸收了 2 和 3……从大到小贪心可保证每个可合并的数字都被最大化合并从而位数最少。为什么「数字升序排列」得到最小整数位数相同的两个正整数比较大小等价于从高位到低位逐位比较字典序。把数字因子按升序排列后最高位最小依次类推因此得到的整数是这些数字所有排列中最小者。这一点与仓库贪心章节「经典例题分发饼干」中「先排序再贪心」的思想一脉相承。边界情况汇总输入num行为说明1 ~ 9直接返回num一位数本身的数位乘积即等于自身含大于 9 的质因子如 11、13、22、26返回 0while循环结束后num 1结果超过 $2^{31}-1$如num 2^{29}附近的大数返回 0溢出检查兜底常规可分解数如 48、15返回最小拼接结果68、35值得注意num 10时答案恰为num本身例如num 8时x 8这是题目定义下唯一且最小的解num 1时同理返回 1。从仓库源码看同类题与延伸《算法通关手册》将本题归类于「贪心、数学」标签与仓库中其他贪心题目如 0455 分发饼干、0860 柠檬水找零、0435 无重叠区间同属一类「局部最优推全局最优」的建模套路问题转化把「构造最小整数」转化为「分解 排序拼接」两个独立子问题贪心策略制定每次取最大可行的一位因子先保位数最少再升序拼接再保高位最小最优子结构利用每次整除后的商仍遵循相同结构递归处理。若想系统补全贪心理论基础贪心选择性质、最优子结构、正确性证明的交换论证法可直接阅读仓库 07_05 贪心算法 章节刷题完成后可回到 贪心算法题目分类列表 继续巩固同类题目。小结LeetCode 0625「最小因式分解」是一道将「数位乘积还原」与贪心思想结合的经典中等题。核心解法只有三条特判一位数 → 从 9 到 2 贪心分解 → 升序拼接并做 32 位溢出检查。掌握这道题的分解合并逻辑不仅能够秒杀本题还能迁移到「将一个数拆成若干合法数字因子使拼接结果最小/最大」一类面试题中是贪心 数论交叉考点的必刷样例。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐AlgoNote 算法通关手册LeetCode 605 种花问题贪心解法全解析AlgoNote 算法通关手册LeetCode 605 种花问题贪心解法全解析 本篇题解源自 AlgoNote 算法通关手册 https://link.git教程文档知识库AlgoNote 算法通关手册LeetCode 0555「分割连接字符串」贪心 枚举题解AlgoNote 算法通关手册LeetCode 0555「分割连接字符串」贪心 枚举题解 本篇是「算法通关手册」AlgoNote 中对 LeetCode教程文档知识库AlgoNote 算法通关手册LeetCode 0670 最大交换Maximum Swap贪心解法深度解析AlgoNote 算法通关手册LeetCode 0670 最大交换Maximum Swap贪心解法深度解析 本文是 AlgoNote「算法通关手册」系列题教程文档知识库上一篇开源仿宋终于来了朱雀仿宋补全「宋黑仿楷」四大字体缺口的完整指南下一篇如何用cc-skills-golang搭建AI代码评审GitHub Actions Claude Code Copilot完整部署指南创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考