263. 丑数

🟢   🔖  数学  🔗 力扣 LeetCode

题目

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，说明是丑数；否则，不是丑数。

1. 定义丑数：

   • 丑数是只包含质因数 2, 3, 和 5 的正整数。
   • 特例：1 是丑数（没有质因数）。

2. 提前排除无效输入：

   • 如果 n <= 0，直接返回 false，因为丑数必须是正整数。

3. 逐步整除：

   • 对于 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+	🟠	🀄️ 🔗