[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(\log n)

在这种方法中,我们将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. 😉😃💗