LeetCode 263. 丑数
题目描述
✅ 263. 丑数
题意分析
丑数是质因子只可能为
2、3、5的正整数，也就是能写成 $2^a3^b5^c$，其中三个指数都是非负整数。允许某种因子完全不出现；三个指数都为零时得到1，它也属于丑数。只需判断给定数字，不必生成丑数序列。把这三个允许的因子全部除掉，检查是否还剩其他因子即可。
解法：反复除以 2、3、5
核心思路
[!blue]
先排除
n <= 0，因为定义要求正整数。尤其是0，它能被任意非零因子整除，但相除后仍为0，不能进入后面的除法循环。依次处理
2、3、5。只要当前因子能整除n，就继续相除，直到它的所有次幂都被除尽。每次相除只删去一个允许的质因子，不会改变是否含有其他质因子；后续除去其他因子也不会重新产生已经除尽的因子。三个因子处理完后，剩余值不再含
2、3、5。若它等于1，原数就完全由允许的因子组成；若它大于1，必然还含某个不允许的质因子，不能是丑数。每次成功相除都会让正整数严格减小，因此循环一定结束。
解题步骤
- 若
n <= 0，直接返回false。- 依次枚举因子
2、3、5；只要当前因子还能整除n，就持续相除。- 三个因子全部处理后，返回
n == 1。
n = 1时三个除法循环都不会进入，最后自然返回true，无需单独分支。
代码实现
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+1))$，每次成功相除都会让
n至少缩小一半；非正数直接返回，为 $O(1)$。- 空间复杂度：$O(1)$。因子集合大小固定为 3。
关键点总结
[!green]
- 除去允许因子保持了“是否含有其他质因子”这一性质。
- 最终判断剩余值是否为
1，不需要把其他质因子逐一找出来。
易错点总结
[!yellow]
- 每种因子都要循环除尽，不能只除一次，也不能因某种因子不存在就判失败。
- 能被一个允许因子整除，只能说明含有该因子，不能排除同时含有其他质因子。
- 负数直接返回
false，不要取绝对值后判断；1则满足定义。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 264. 丑数 II | 中等 | 原题按序生成第n个丑数，本题只判断一个数能否完全除去2、3、5三个因子。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！