Swift - LeetCode - 丑数
2022-08-22 本文已影响0人
晨曦的简书
题目
丑数 就是只包含质因数 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。
方法一：数学
思路及解法
根据丑数的定义，0 和负整数一定不是丑数。
当 时，若
是丑数，则
可以写成
的形式，其中
,
,
都是非负整数。特别地，当
,
,
都是
时，
。
为判断 是否满足上述形式，可以对
反复除以
,
,
，直到
不再包含质因数
,
,
。若剩下的数等于
，则说明
不包含其他质因数，是丑数；否则，说明
包含其他质因数，不是丑数。
代码
class Solution {
func isUgly(_ n: Int) -> Bool {
var n: Int = n
if n <= 0 {
return false
}
let factors: [Int] = [2, 3, 5]
for factor in factors {
while n % factor == 0 {
n /= factor
}
}
return n == 1
}
}
复杂度分析
-
时间复杂度：
。时间复杂度取决于对
除以
,
,
的次数，由于每次至少将
-
空间复杂度：
。
方法二：数学（二）
思路及解法
判断当前 是否可以整除
，如果可以将
；再判断是否可以整除
，如果可以将
；判断是否可以整除
，可以的话将
；
如果符合丑数只包含 或
或
的定义则最终的
值一定等于
。
代码
class Solution {
func isUgly(_ n: Int) -> Bool {
var n: Int = n
while n >= 1 {
if n % 2 == 0 {
n /= 2
} else if n % 3 == 0 {
n /= 3
} else if n % 5 == 0 {
n /= 5
} else {
break
}
}
return n == 1
}
}
复杂度分析
-
时间复杂度：
-
空间复杂度：
