学习笔记|丑数系列算法-1

以下文章来源于labuladong ，作者labuladong

首先，「丑数」系列问题属于会者不难难者不会的类型，因为会用到些数学定理嘛，如果没有专门学过，靠自己恐怕是想不出来的。

另外，这类问题而且非常考察抽象联想能力，因为它除了数学定理之外，还需要你把题目抽象成链表相关的题目运用双指针技巧，或者抽象成数组相关的题目运用二分搜索技巧。

那么今天我就来用一篇文章把所有丑数相关的问题一网打尽，看看这类问题能够如何变化，应该如何解决。

丑数 I

首先是力扣第 263 题「丑数」，题目给你输入一个数字n，请你判断n是否为「丑数」。所谓「丑数」，就是只包含质因数2、3和5的正整数。

函数签名如下：

boolean isUgly(int n)

比如 12 = 2 x 2 x 3 就是一个丑数，而 42 = 2 x 3 x 7 就不是一个丑数。

这道题其实非常简单，前提是你知道算术基本定理（正整数唯一分解定理）：

任意一个大于 1 的自然数，要么它本身就是质数，要么它可以分解为若干质数的乘积。

既然任意一个大于一的正整数都可以分解成若干质数的乘积，那么丑数也可以被分解成若干质数的乘积，且这些质数只能是 2, 3 或 5。

有了这个思路，就可以实现isUgly函数了：

public boolean isUgly(int n) {
    if (n <= 0) return false;
    // 如果 n 是丑数，分解因子应该只有 2, 3, 5
    while (n % 2 == 0) n /= 2;
    while (n % 3 == 0) n /= 3;
    while (n % 5 == 0) n /= 5;
    // 如果能够成功分解，说明是丑数
    return n == 1;
}