河东做网站,网站建站代码,百度seo公司,stanley工具网站开发文章目录 写在前面Tag题目来源题目解读解题思路方法一#xff1a;数学优化计算 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法#xff0c;两到三天更新一篇文章#xff0c;欢迎催更…… 专栏内容以分析题目为主#xff0c;并附带一些对于本题涉及到的数据结… 文章目录 写在前面Tag题目来源题目解读解题思路方法一数学优化计算 写在最后 写在前面 本专栏专注于分析与讲解【面试经典150】算法两到三天更新一篇文章欢迎催更…… 专栏内容以分析题目为主并附带一些对于本题涉及到的数据结构等内容进行回顾与总结文章结构大致如下部分内容会有增删 Tag介绍本题牵涉到的知识点、数据结构题目来源贴上题目的链接方便大家查找题目并完成练习题目解读复述题目确保自己真的理解题目意思并强调一些题目重点信息解题思路介绍一些解题思路每种解题思路包括思路讲解、实现代码以及复杂度分析知识回忆针对今天介绍的题目中的重点内容、数据结构进行回顾总结。 Tag
【数学-阶乘】 题目来源
172. 阶乘后的零 题目解读
给你一个整数 n求出 n! 的结果中尾部 0 的数量其中 n ! n ∗ ( n − 1 ) ∗ ( n − 2 ) ∗ . . . ∗ 3 ∗ 2 ∗ 1 n!n*(n-1)*(n-2)*...*3*2*1 n!n∗(n−1)∗(n−2)∗...∗3∗2∗1 解题思路
学习 官方题解.
方法一数学优化计算
n! 尾零的数量即为 n! 中因子 10 的个数而 10 2 x 5因此转换成求 n! 中质因子 2 的个数和 质因子 5 的个数的较小值。
由于质因子 5 的个数不会大于质因子 2 的个数证明如下我们可以仅考虑质因子 5 的个数 。n! 中质因子 5 的个数等于 [1, n] 的每个数的质因子 5 的个数之和我们可以遍历 [1, n] 的所有 5 的倍数求出。
代码 1
class Solution {
public:int trailingZeroes(int n) {int cout_5 0;for (int i 5; i n; i 5) {int cur i;while (cur % 5 0) {cout_5;cur / 5;} }return cout_5;}
};证明
[1, n] 中 p 的倍数有 n 1 ⌊ n p ⌋ n_1 \lfloor{\frac{n}{p}} \rfloor n1⌊pn⌋这些数至少贡献出了 n 1 n_1 n1 个质因子 p。一般地[1, n] 中质因子 p 的个数为 ∑ k 1 ∞ ⌊ n p k ⌋ \sum_{k1}^{\infty}{\lfloor \frac{n}{p^k} \rfloor} k1∑∞⌊pkn⌋
上式表明n 不变p 越大质因子的个数越小因此 [1, n] 中质因子 5 的个数不会大于质因子 2 的个数。证毕。
优化
[1, n] 中质因子 5 的个数为 ∑ k 1 ∞ ⌊ n 5 k ⌋ \sum_{k1}^{\infty}{\lfloor \frac{n}{5^k} \rfloor} k1∑∞⌊5kn⌋
因此我们可以通过不断将 n 除以 5并将结果累加即得到答案。
代码 2
class Solution {
public:int trailingZeroes(int n) {int res 0;while (n) {n / 5;res n;}return res;}
};复杂度分析
时间复杂度 O ( n ) O(n) O(n)。优化后的时间复杂度为 O ( l o g n ) O(logn) O(logn)。
空间复杂度 O ( 1 ) O(1) O(1)。 写在最后
如果您发现文章有任何错误或者对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度的方法欢迎评论区交流。
最后感谢您的阅读如果有所收获的话可以给我点一个 哦。
