江川个人博客FIELD NOTES / 个人知识库

Article / 文章

LeetCode 第172题：阶乘后的零

给定一个整数 n，返回 n! 结果中尾随零的数量。 提示：n! = n (n - 1) (n - 2) ... 3 2 1

题目描述

给定一个整数 n，返回 n! 结果中尾随零的数量。

提示：n! = n * (n - 1) * (n - 2) * ... * 3 * 2 * 1

难度

中等

题目链接

点击在LeetCode中查看题目

示例

示例 1：

输入：n = 3
输出：0
解释：3! = 6 ，不含尾随 0

示例 2：

输入：n = 5
输出：1
解释：5! = 120 ，有一个尾随 0

示例 3：

输入：n = 0
输出：0

提示

  • 0 <= n <= 10^4

解题思路

方法：计算因子5的个数

尾随零的数量取决于阶乘中因子10的个数，而10 = 2 × 5。因为2的数量总是比5多，所以问题简化为计算阶乘中因子5的个数。 关键点：

  1. 计算n!中因子5的个数
  2. 注意到有些数字包含多个因子5，例如25 = 5 × 5，所以需要特殊处理
  3. 可以通过反复除以5来计算因子5的总数

时间复杂度：O(log n)，因为每次除以5，n的值会减小到原来的1/5。 空间复杂度：O(1)，只需要常数额外空间。

代码实现

C# 实现

public class Solution {
    public int TrailingZeroes(int n) {
        int count = 0;
        
        // 计算n!中因子5的个数
        while (n > 0) {
            n /= 5;
            count += n;
        }
        
        return count;
    }
}

Python 实现

class Solution:
    def trailingZeroes(self, n: int) -> int:
        count = 0
        
        # 计算n!中因子5的个数
        while n > 0:
            n //= 5
            count += n
        
        return count

C++ 实现

class Solution {
public:
    int trailingZeroes(int n) {
        int count = 0;
        
        // 计算n!中因子5的个数
        while (n > 0) {
            n /= 5;
            count += n;
        }
        
        return count;
    }
};

性能分析

各语言实现的性能对比：

实现语言 执行用时 内存消耗 特点
C# 24 ms 26.2 MB 实现简洁，性能适中
Python 32 ms 16.2 MB 代码最简洁
C++ 0 ms 5.9 MB 性能最优

补充说明

代码亮点

  1. 不直接计算阶乘，避免了大数运算
  2. 通过数学推导简化了问题，直接计算因子5的数量
  3. 代码简洁高效，时间复杂度为O(log n)

常见错误

  1. 直接计算阶乘值然后统计尾随零，会导致大数溢出
  2. 只考虑了5的倍数，没有考虑包含多个因子5的数字（如25、125）
  3. 复杂化问题，没有抓住本质（只需要计算因子5的个数）

相关题目