263. 丑数
263. 丑数
题目
An ugly number is a positive integer whose prime factors are limited to 2
, 3
, and 5
.
Given an integer n
, return true
if n
is anugly number.
Example 1:
Input: n = 6
Output: true
Explanation: 6 = 2 × 3
Example 2:
Input: n = 1
Output: true
Explanation: 1 has no prime factors, therefore all of its prime factors are limited to 2, 3, and 5.
Example 3:
Input: n = 14
Output: false
Explanation: 14 is not ugly since it includes the prime factor 7.
Constraints:
-2^31 <= n <= 2^31 - 1
题目大意
丑数 就是只包含质因数 2
、3
和 5
的正整数。
给你一个整数 n
,请你判断 n
是否为 丑数 。如果是,返回 true
;否则,返回 false
。
示例 1:
输入: n = 6
输出: true
解释: 6 = 2 × 3
示例 2:
输入: n = 1
输出: true
解释: 1 没有质因数,因此它的全部质因数是 {2, 3, 5} 的空集。习惯上将其视作第一个丑数。
示例 3:
输入: n = 14
输出: false
解释: 14 不是丑数,因为它包含了另外一个质因数 7 。
提示:
-2^31 <= n <= 2^31 - 1
解题思路
这道题的核心是利用质因数分解的思想,逐步被 2
, 3
, 和 5
整除,直到无法整除为止。如果整除后剩下的数为 1
,说明是丑数;否则,不是丑数。
定义丑数:
- 丑数是只包含质因数
2
,3
, 和5
的正整数。 - 特例:
1
是丑数(没有质因数)。
- 丑数是只包含质因数
提前排除无效输入:
- 如果
n <= 0
,直接返回false
,因为丑数必须是正整数。
- 如果
逐步整除:
- 对于
n > 0
,不断用2
,3
, 和5
依次整除n
,直到无法整除为止。 - 如果最后的结果是
1
,说明n
只包含2
,3
, 和5
,因此是丑数。 - 否则,
n
包含其他质因数,不是丑数。
- 对于
复杂度分析
- 时间复杂度:
O(log n)
,其中n
是输入数值,主循环最多运行log_2(n) + log_3(n) + log_5(n)
次,因为每次将n
除以因数2
,3
, 或5
。 - 空间复杂度:
O(1)
,只使用常数空间。
代码
/**
* @param {number} n
* @return {boolean}
*/
var isUgly = function (n) {
if (n <= 0) return false; // 丑数必须是正整数
const factors = [2, 3, 5]; // 定义允许的质因数
for (const factor of factors) {
while (n % factor === 0) {
// 不断整除因数
n /= factor;
}
}
return n === 1; // 如果最终结果为1,则是丑数
};
相关题目
题号 | 标题 | 题解 | 标签 | 难度 | 力扣 |
---|---|---|---|---|---|
202 | 快乐数 | [✓] | 哈希表 数学 双指针 | 🟢 | 🀄️ 🔗 |
204 | 计数质数 | 数组 数学 枚举 1+ | 🟠 | 🀄️ 🔗 | |
264 | 丑数 II | [✓] | 哈希表 数学 动态规划 1+ | 🟠 | 🀄️ 🔗 |