题目分析LeetCode 172. 阶乘后的零给定一个整数 n返回 n!n 的阶乘结果尾数中零的数量。示例输入n 5输出1因为 5! 120尾数有 1 个零输入n 3输出0因为 3! 6没有尾随零核心思路尾随零由因子 10 2 × 5 产生。在阶乘中因子 2 的数量远多于因子 5 的数量因此尾随零的数量等于因子 5 的个数。需要注意的是像 25、125、625 这样的数包含多个因子 525 5² 贡献 2 个125 5³ 贡献 3 个需要重复计数。计算公式为尾随零数量 n/5 n/25 n/125 n/625 …Java 实现方法一循环迭代推荐class Solution {public int trailingZeroes(int n) {int count 0;while (n 0) {n / 5; // 计算当前5的幂次对应的倍数个数count n; // 累加因子5的数量}return count;}}执行过程以 n 100 为例第1轮n 100/5 20count 205 的倍数有 20 个第2轮n 20/5 4count 2425 的倍数有 4 个第3轮n 4/5 0终止结果24 个尾随零方法二递归写法class Solution {public int trailingZeroes(int n) {return n 0 ? 0 : n / 5 trailingZeroes(n / 5);}}复杂度分析维度 复杂度 说明时间复杂度 O(log₅n) 每次循环 n 除以 5循环次数为 log₅n空间复杂度 O(1) 仅使用常数个变量递归版为 O(log₅n) 栈空间常见错误解法错误思路先算阶乘再数零// ❌ 不推荐n 稍大就会溢出即使使用 BigInteger 效率也很低BigInteger factorial BigInteger.ONE;for (int i 2; i n; i) {factorial factorial.multiply(BigInteger.valueOf(i));}// 再转字符串数尾随零…这种方法时间复杂度 O(n)且大数阶乘会占用大量内存完全不符合题目要求的对数时间复杂度。面试延伸如果面试官追问可以补充说明为什么不用统计因子 2 因为在 1~n 中偶数含因子 2的数量远多于 5 的倍数因子 2 永远充足瓶颈在因子 5。如果题目改为统计末尾非零数字 那就需要更复杂的数学推导涉及模运算和周期性规律。如果 n 非常大如 10⁹ 当前解法依然高效因为 log₅(10⁹) ≈ 13只需循环 13 次。要不要顺带说说末尾非零数字那道题的解法思路和这题属于同一类数学推导。
