[Leetcode][172. 阶乘后的零] 3种方法:暴力大数,计算5的个数,对数时间复杂度
By Long Luo
Leetcode 172. 阶乘后的零 题解:
方法一:用大数暴力求解并计算末尾0的数量
因为 得到的数字会非常大,所以需要使用BigInteger
,得到结果之后,再计算末尾 的数量。
1 | import java.math.BigInteger; |
复杂度分析
-
时间复杂度:, 实际上应该是 ,但 很快,只有 ,所以 .
-
空间复杂度:。
方法二:计算1到n中全部5因子数量
思路与算法:
考虑到计算阶乘末尾的每个 表示乘以 ,那么在我们在计算 时乘以 的次数是多少?
考虑到两个数字 和 相乘,例如,要执行 ,我们可以将其分解为:
从上面可以得出,我们只需要考虑 的因子有多少对。同时,因为 的因子数比 的因子数要多,所以我们只需要计算 到 的 的因子数有多少即可。
1 | public int trailingZeroes(int n) { |
复杂度分析
- 时间复杂度:。
为了计算零计数,我们循环从 到 的每五个数字处理一次,这里是 步。
在每个步骤中,虽然看起来像是执行 操作来计算 的因子数,但实际上它只消耗 ,因为绝大部分的数字只包含一个因子 。可以证明,因子 的总数小于 。
所以我们得到 。
- 空间复杂度:。
方法三:对数时间复杂度
方法二还可以进一步改进,因为我们实际上只对 的因子感兴趣,而方法二需要每个 的倍数进行计算。那么,如何解决有多重因子的数字呢?
所有包含两个及以上的因子 的数字都是 的倍数。所以我们可以简单的除以 来计算 的倍数是多少。
我们每次将 本身除以 ,这样可以得到一个系列:
1 | public static int trailingZeroes(int n) { |
复杂度分析
- 时间复杂度:。
在这种方法中,我们将 除以 的每个幂。根据定义, 的 幂小于或等于 。由于乘法和除法在32位整数范围内,我们将这些计算视为 。因此,我们正在执行 操作。
- 空间复杂度:,只是用了常数空间。
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. 😉😃💗