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

Article / 文章

LeetCode 第263题：丑数

编写一个程序判断给定的数是否为丑数。 丑数就是只包含质因数 2, 3, 5 的正整数。

📖 文章摘要

本文详细解析LeetCode第263题“丑数”，这是一道数学问题。文章提供了简洁高效的除法判断解法，包含C#、Python、C++、JavaScript四种语言实现，配有详细的算法步骤图解和性能分析。适合算法初学者和想要掌握基础数学算法的开发者。

核心知识点： 数学运算、除法操作、循环控制
难度等级： 简单
推荐人群： 算法初学者、编程基础学习者

题目描述

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例

示例 1：

输入: 6
输出: true
解释: 6 = 2 × 3

示例 2：

输入: 8
输出: true
解释: 8 = 2 × 2 × 2

示例 3：

输入: 14
输出: false
解释: 14 不是丑数，因为它包含了另外一个质因数 7。

提示

  • -2^31 <= num <= 2^31 - 1
  • 1 通常被视为丑数。

解题思路

丑数的定义是只包含质因数 2、3、5 的正整数。根据这个定义，我们可以通过不断除以 2、3 和 5 来检查一个数是否为丑数。如果最后剩下的数是 1，那么这个数就是丑数；否则，它就不是丑数。

方法：除法判断

核心思想：

  1. 如果给定的数 num 小于等于 0，则它不是丑数，直接返回 false
  2. 如果 num 等于 1，根据定义，它是丑数，直接返回 true
  3. 循环处理：只要 num 能被 2 整除，就将其除以 2；只要 num 能被 3 整除，就将其除以 3；只要 num 能被 5 整除，就将其除以 5
  4. 处理完所有可能的 2、3、5 因子后，检查剩余的数是否为 1。如果是 1，则原始数是丑数；否则，它不是丑数

算法优化：

  • 使用循环和数组来简化代码结构
  • 先处理边界情况，提高代码健壮性
  • 使用迭代方式避免递归栈溢出风险

复杂度分析：

  • 时间复杂度：O(log n)，其中 n 是输入的数字。最坏情况下，n 的每一位都是 2、3 或 5 的因子，我们需要执行 log n 次除法
  • 空间复杂度：O(1)，只使用了常数级别的额外空间

图解思路

算法步骤分析表

步骤 输入示例 操作 结果 说明
初始状态 num = 12 检查边界条件 num > 0，继续 12是正数，可能是丑数
第一轮 num = 12 除以2直到不能整除 num = 3 12 ÷ 2 ÷ 2 = 3
第二轮 num = 3 除以3直到不能整除 num = 1 3 ÷ 3 = 1
第三轮 num = 1 除以5直到不能整除 num = 1 1不能被5整除，保持不变
结果判断 num = 1 检查是否为1 true 最终结果为1，是丑数

不同情况分析表

输入 质因数分解 处理过程 最终结果 是否丑数
6 2 × 3 6→3→1 1 是
8 2³ 8→4→2→1 1 是
14 2 × 7 14→7 7 否（包含质因数7）
1 无 直接返回 1 是（特殊情况）
0 无意义 边界检查 false 否（非正数）

代码实现

C# 实现

public class Solution {
    public bool IsUgly(int num) {
        // 非正数不是丑数
        if (num <= 0) {
            return false;
        }
        
        // 循环除以2、3、5，直到不能整除为止
        int[] factors = {2, 3, 5};
        foreach (int factor in factors) {
            while (num % factor == 0) {
                num /= factor;
            }
        }
        
        // 如果最后剩下1，则是丑数；否则不是
        return num == 1;
    }
}

Python 实现

class Solution:
    def isUgly(self, num: int) -> bool:
        # 非正数不是丑数
        if num <= 0:
            return False
        
        # 循环除以2、3、5，直到不能整除为止
        for factor in [2, 3, 5]:
            while num % factor == 0:
                num //= factor
        
        # 如果最后剩下1，则是丑数；否则不是
        return num == 1

C++ 实现

class Solution {
public:
    bool isUgly(int num) {
        // 非正数不是丑数
        if (num <= 0) {
            return false;
        }
        
        // 循环除以2、3、5，直到不能整除为止
        int factors[] = {2, 3, 5};
        for (int factor : factors) {
            while (num % factor == 0) {
                num /= factor;
            }
        }
        
        // 如果最后剩下1，则是丑数；否则不是
        return num == 1;
    }
};

JavaScript 实现

/**
 * @param {number} num
 * @return {boolean}
 */
var isUgly = function(num) {
    // 非正数不是丑数
    if (num <= 0) {
        return false;
    }
    
    // 循环除以2、3、5，直到不能整除为止
    const factors = [2, 3, 5];
    for (const factor of factors) {
        while (num % factor === 0) {
            num /= factor;
        }
    }
    
    // 如果最后剩下1，则是丑数；否则不是
    return num === 1;
};

执行结果

C# 实现

  • 执行用时：24 ms
  • 内存消耗：15.1 MB

Python 实现

  • 执行用时：32 ms
  • 内存消耗：13.6 MB

C++ 实现

  • 执行用时：0 ms
  • 内存消耗：5.9 MB

JavaScript 实现

  • 执行用时：68 ms
  • 内存消耗：38.1 MB

性能对比

语言 执行用时 内存消耗 特点
C++ 0 ms 5.9 MB 性能最佳，内存占用最小
C# 24 ms 15.1 MB 性能中等，语法简洁清晰
Python 32 ms 13.6 MB 代码最简洁，易于理解
JavaScript 68 ms 38.1 MB 性能较差，内存占用最大

代码亮点

  1. 🎯 算法简洁明了，逻辑清晰，易于理解和实现
  2. 💡 使用循环和数组优化代码结构，提高代码可读性
  3. 🔍 优先处理边界情况（非正数），提高代码健壮性
  4. 🎨 采用迭代方式而非递归，避免栈溢出风险

常见错误分析

  1. 🚫 忘记处理非正数的情况，导致对0或负数判断错误
  2. 🚫 未考虑1是丑数的特殊情况，直接返回false
  3. 🚫 在循环中使用不必要的条件判断，增加时间复杂度
  4. 🚫 使用递归实现，可能导致栈溢出问题

解法对比

解法 时间复杂度 空间复杂度 优点 缺点
迭代除法 O(log n) O(1) 简单易懂，效率高 无明显缺点
递归除法 O(log n) O(log n) 代码简洁 存在栈溢出风险
质因数分解 O(sqrt(n)) O(1) 适用于更一般的因数分解问题 对于本题过于复杂

相关题目

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第263题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

  • 👍 点个赞，让更多人看到这篇文章
  • 📁 收藏文章，方便后续查阅复习
  • 🔔 关注作者，获取更多高质量算法题解
  • 💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！