算法学习之旅
问题：设计一个算法，计算出n阶乘中尾部零的个数
例如: 11! = 39916800，因此应该返回 2
挑战：O(logN)的时间复杂度
想法1：
找出1–n中每个数字能够被5或者10整除的次数，加在一起就是答案。但是时间复杂度是O(N2).代码如下：`public static long trailingZeros(long n) {
// write your code here
long five=0;
long count=0;
for(long i=1;i<=n;i++){
if(i%10==0){
long j=i;
while(j>1 && j%10==0){
j/=10;
count++;
}
if(j%5==0){
while(j>1 && j%5==0){
j/=5;
count++;
}
}
}else if(i%5==0){
long k=i;
while(k>1 && k%5==0){
k/=5;
count++;
}
}
}return count;}
想法2.统计1—n 能被5整除的次数，累加求和，代码类似上边
想法3：对想法2进行优化，只对1—n之中能够被5整除的数进行统计。代码如下：
public static long trailingZeros(long n) {
// write your code here
long five=0;
long count=0;
if(n<5)\{
return 0;
\}else if(n==5)\{
return 1;
\}
for(long i=5;i<=n;i+=5)\{
if(i%5==0)\{
long j=i;
while(j>0 && j%5==0){
j/=5;
count++;
}
}
}
return count;
}
《编程之美》上的想法3：
公式：Z = [N/5] +[N/52] +[N/53] + …（不用担心这会是一个无穷的运算，因为总存在一个K，使得5K > N，[N/5K]=0。）
5的倍数贡献一个5，5的平方贡献两个5~~~.
代码如下：
int num = 0, i;
for(i=5; i<=n; i*=5)
{
num += n/i;
}
return num;
又简洁，执行效率又高，与君共勉之。
淩亂°似流年
深藏阁楼爱情的钟
以你之姓@
亦凉
超、凢脫俗
还没有评论，来说两句吧...