By Long Luo
172. 阶乘后的零题目如下所示：
- 阶乘后的零
给定一个整数 n ，返回 n! 结果中尾随零的数量。
提示 n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1
示例 1：
输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0
示例 2：
输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0
示例 3：
输入：n = 0
输出：0
提示：
0 <= n <= 10^4
进阶：你可以设计并实现对数时间复杂度的算法来解决此问题吗？
方法一：计算1到n中全部5因子数量
思路与算法：
考虑到计算阶乘末尾的每个0表示乘以10，那么在我们在计算n!时乘以10的次数是多少？
考虑到两个数字a和b相乘，例如，要执行15 x 24 = 360，我们可以将其分解为：
15 x 24 = 3 x 5 x 2 x 2 x 2 x 3 = 360
从上面可以得出，我们只需要考虑2 x 5的因子有多少对。同时，因为2的因子数比5的因子数要多，所以我们只需要计算1到n的5的因子数有多少即可。
代码如下所示：
public int trailingZeroes(int n) {
int ans = 0;
for (int i = 5; i <= n; i += 5) {
int temp = i;
while (temp % 5 == 0) {
ans++;
temp /= 5;
}
}
return ans;
}
复杂度分析：
- 时间复杂度：
。
为了计算零计数，我们循环从5到n的每五个数字处理一次，这里是O(n)步。
在每个步骤中，虽然看起来像是执行操作来计算5的因子数，但实际上它只消耗
，因为绝大部分的数字只包含一个因子5。可以证明，因子5的总数小于
。
所以我们得到O(n) x O(1) = O(n)。
- 空间复杂度：
，只是用了一个整数变量。
方法二：
方法一还可以进一步改进，因为我们实际上只对5的因子感兴趣，而方法二需要每个5的倍数进行计算。那么，如何解决有多重因子的数字呢？
所有包含两个及以上的因子5的数字都是25的倍数。所以我们可以简单的除以25来计算25的倍数是多少。
我们每次将n本身除以5，这样可以得到一个系列：
n / 5 + n / 25 + n / 125 + ...
代码如下所示：
public static int trailingZeroes(int n) {
int ans = 0;
while (n > 0) {
n /= 5;
ans += n;
}
return ans;
}
复杂度分析：
- 时间复杂度：
。
在这种方法中，我们将除以
的每个幂。根据定义，
幂小于或等于
操作
- 空间复杂度：
网友评论