[Leetcode][172. 阶乘后的零] 3种方法:暴力大数,计算5的个数,对数时间复杂度

By Long Luo

Leetcode 172. 阶乘后的零 题解:

方法一:用大数暴力求解并计算末尾0的数量

因为 n!n! 得到的数字会非常大,所以需要使用BigInteger,得到结果之后,再计算末尾 00 的数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.math.BigInteger;

class Solution {
public int trailingZeroes(int n) {
BigInteger nFactorResult = BigInteger.ONE;
for (int i = 2; i <= n; i++) {
nFactorResult = nFactorResult.multiply(BigInteger.valueOf(i));
}

int ans = 0;
while (nFactorResult.mod(BigInteger.TEN).equals(BigInteger.ZERO)) {
ans++;
nFactorResult = nFactorResult.divide(BigInteger.TEN);
}

return ans;
}
}

复杂度分析

  • 时间复杂度:O(n)O(n), 实际上应该是 O(n+logn)O(n + logn),但 lognlogn 很快,只有 O(1)O(1),所以 O(n)O(n).

  • 空间复杂度:O(1)O(1)

方法二:计算1到n中全部5因子数量

思路与算法:

考虑到计算阶乘末尾的每个 00 表示乘以 1010,那么在我们在计算 n!n! 时乘以 1010 的次数是多少?
考虑到两个数字 aabb 相乘,例如,要执行 15×24=36015 \times 24 = 360,我们可以将其分解为:

15×24=3×5×2×2×2×3=36015 \times 24 = 3 \times 5 \times 2 \times 2 \times 2 \times 3 = 360

从上面可以得出,我们只需要考虑 2×52 \times 5 的因子有多少对。同时,因为 22 的因子数比 55 的因子数要多,所以我们只需要计算 11nn55 的因子数有多少即可。

1
2
3
4
5
6
7
8
9
10
11
12
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;
}

复杂度分析

  • 时间复杂度:O(n)O(n)

为了计算零计数,我们循环从 55nn 的每五个数字处理一次,这里是 O(n)O(n) 步。
在每个步骤中,虽然看起来像是执行 O(logn)O(logn) 操作来计算 55 的因子数,但实际上它只消耗 O(1)O(1),因为绝大部分的数字只包含一个因子 55。可以证明,因子 55 的总数小于 2n5\frac{2 \cdot n}{5}
所以我们得到 O(n)×O(1)=O(n)O(n) \times O(1) = O(n)

  • 空间复杂度:O(1)O(1)

方法三:对数时间复杂度

方法二还可以进一步改进,因为我们实际上只对 55 的因子感兴趣,而方法二需要每个 55 的倍数进行计算。那么,如何解决有多重因子的数字呢?

所有包含两个及以上的因子 55 的数字都是 2525 的倍数。所以我们可以简单的除以 2525 来计算 2525 的倍数是多少。

我们每次将 nn 本身除以 55,这样可以得到一个系列:

n/5+n/25+n/125+...n / 5 + n / 25 + n / 125 + ...

1
2
3
4
5
6
7
8
9
public static int trailingZeroes(int n) {
int ans = 0;
while (n > 0) {
n /= 5;
ans += n;
}

return ans;
}

复杂度分析

  • 时间复杂度:O(logn)O(logn)

在这种方法中,我们将 nn 除以 55 的每个幂。根据定义,55log5n\log_5n 幂小于或等于 nn。由于乘法和除法在32位整数范围内,我们将这些计算视为 O(1)O(1)。因此,我们正在执行 log5nO(1)=logn\log_5 n \cdot O(1) =\log n操作。

  • 空间复杂度:O(1)O(1),只是用了常数空间。

All suggestions are welcome.
If you have any query or suggestion please comment below.
Please upvote👍 if you like💗 it. Thank you:-)

Explore More Leetcode Solutions. 😉😃💗