跳至主要內容

263. 丑数


263. 丑数

🟢   🔖  数学  🔗 力扣open in new window LeetCodeopen in new window

题目

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

题目大意

丑数 就是只包含质因数 235 的正整数。

给你一个整数 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快乐数[✓]哈希表 数学 双指针🟢🀄️open in new window 🔗open in new window
204计数质数数组 数学 枚举 1+🟠🀄️open in new window 🔗open in new window
264丑数 II[✓]哈希表 数学 动态规划 1+🟠🀄️open in new window 🔗open in new window