LeetCode 263. 丑数
目录
题目描述
✅ 263. 丑数
题意分析
给一个整数
n，判断它是不是「丑数」。丑数的定义是正整数，且它的质因数只能来自2、3、5这三个数。返回布尔值，不需要给出分解过程。约束信号有两条。一是「正整数」，所以
0和负数一律不合法，必须在动手计算之前就拦掉；二是质因数被限定在一个很小的固定集合里，不需要考虑通用的质因数分解，也不需要判素数。边界值有三个要特别想：
n = 1没有任何质因数，空集合天然满足「质因数都在 {2, 3, 5} 中」，所以 1 是丑数；n = 0会让任何「能否整除」的判断恒真，是死循环的高发点；n取到 32 位上界时循环次数也很有限，不必担心超时。
解法：反复除以 2、3、5
核心思路
题目只需判断是否存在
2、3、5以外的质因子，无须做通用质因数分解。依次把这三个允许的因子除尽，检查剩余部分是否为1即可。循环不变量：任意时刻，当前
n等于原数除以若干个已经剥离的2、3、5，所以除法不会改变「是否含有其他质因子」这一事实。三个因子都除尽后：
- 若
n == 1，原数可以写成 $2^a \times 3^b \times 5^c$，是丑数；- 若
n > 1，剩余部分一定含有其他质因子，不是丑数。必须先排除
n <= 0。它们不符合正整数定义，且0对任意因子取模都是0，直接进入循环会永远除不完。
解题步骤
- 若
n <= 0，直接返回false。- 依次枚举因子
2、3、5；只要当前因子还能整除n，就持续相除。- 三个因子全部处理后，返回
n == 1。例如
60 → 30 → 15 → 5 → 1，所有因子都能被剥离，因此返回true；14 → 7后再也除不动，剩余质因子7，因此返回false。
代码实现
class Solution {
public boolean isUgly(int n) {
if (n <= 0) {
return false;
}
int[] factors = {2, 3, 5};
for (int factor : factors) {
while (n % factor == 0) {
n /= factor;
}
}
return n == 1;
}
}
func isUgly(n int) bool {
if n <= 0 {
return false
}
factors := []int{2, 3, 5}
for _, factor := range factors {
for n%factor == 0 {
n /= factor
}
}
return n == 1
}
复杂度分析
- 时间复杂度：$O(\log n)$。每次成功相除都会让
n至少缩小一半。- 空间复杂度：$O(1)$。因子集合大小固定为 3。
关键点总结
- 判定质因子是否属于固定集合时，可以反向除尽允许因子，再检查剩余值。
- 同一质因子可能重复出现，必须用
while，不能只除一次。1的质因数集合为空，满足定义；0和负数不是正整数。- 本题是判定问题；若改为求第
k个丑数，应使用三指针动态规划生成序列。
易错点总结
- 没有提前拦截
0：0 % factor == 0且相除后仍是0，循环永远不会结束。- 每个因子只除一次：
8只除一次会剩下4，从而把丑数误判为false。- 只要能被一个允许因子整除就返回
true：14能被2整除，但还含有质因子7。- 把
1判为false：1没有质因子，满足「质因子只能是 2、3、5」。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 264. 丑数 II | 中等 | 从判定转为生成，三指针递推出第 n 个丑数 |
| 313. 超级丑数 | 中等 | 质因子集合改为任意给定数组，指针数量随之可变 |
| 1201. 丑数 III | 中等 | 只要求被三个数之一整除，改用二分加容斥计数 |