【LeetCode】263.丑数 & 264. 丑数 II

I. 263. 丑数（是否为丑数）

一、题目描述

编写一个程序判断给定的数是否为丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: 6 输出: true 解释: 6 = 2 × 3

示例 2:

输入: 8 输出: true 解释: 8 = 2 × 2 × 2

示例 3:

输入: 14 输出: false 解释: 14 不是丑数，因为它包含了另外一个质因数 7。

说明：

1 是丑数。输入不会超过 32 位有符号整数的范围: $[-2^{31},2^{31}-1]$。

二、解题思路 & 代码

2.1 循环迭代

class Solution: def isUgly(self, num: int) -> bool: if(num==0): return False if(num==1): return True while(num%2==0): num //=2 while(num%3==0): num //=3 while(num%5==0): num //=5 return num==1

2.2 递归

class Solution: def isUgly(self, num: int) -> bool: if(num==0): return False if(num==1): return True if(num%2==0): return self.isUgly(num // 2) if(num%3==0): return self.isUgly(num // 3) if(num%5==0): return self.isUgly(num // 5) return False

======================================================

II. 264. 丑数（找第 $n$ 个丑数）

一、题目描述

写一个程序，找出第 n 个丑数。

丑数就是质因数只包含 2, 3, 5 的正整数。

示例:

输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

1 是丑数。n 不超过1690。

二、解题思路 & 代码

2.1 动态规划

$dp[i]$ 表示第 i 个丑数 前面的每一个数（状态）都可以乘上 2, 3, 5 来形成一个新的状态

创建 3 个指针 p2、p3、p5，分别表示这 3 个质数因子此时应该乘上第几个状态。

p2、p3、p5 的含义

实际上 $pi$ 的含义是有资格同 $i$ 相乘的最小丑数的位置。

这里资格指的是：如果一个丑数 $dp[pi]$ 通过乘以 $i$ 可以得到下一个丑数，那么这个丑数 $dp[pi]$ 就永远失去了同 $i$ 相乘的资格（没有必要再乘了），我们把 $pi++$ 让 $dp[pi]$ 指向下一个丑数即可。

举例说明：

一开始，丑数只有{1}，1可以同 2 、3 、5 相乘，取最小的 1 × 2 = 2 添加到丑数序列中。现在丑数中有 {1，2} ，在上一步中，1 已经同 2 相乘过了，所以今后没必要再比较 1 × 2 了，我们说 1 失去了同 2 相乘的资格。现在 1 有与 3、5 相乘的资格，2 有与 2、3、5 相乘的资格，但是 2 × 3 和 2 × 5 是没必要比较的，因为有比它更小的 1 可以同 3、5 相乘，所以我们只需要比较 1 × 3 、1 × 5 、 2 × 2 。

依此类推，每次我们都分别比较有资格同 2、3、5 相乘的最小丑数，选择最小的那个作为下一个丑数，假设选择到的这个丑数是同 i（ i = 2、3、5）相乘得到的，所以它失去了同 i 相乘的资格，把对应的 pi++ ，让 pi 指向下一个丑数即可。

class Solution: def nthUglyNumber(self, n: int) -> int: if( n < 1): return 0 p2 = 0 p3 = 0 p5 = 0 dp = [0] * n dp[0] = 1 for i in range(1, n): # 比较此时可能的状态，取最小的那个 dp[i] = min(dp[p2] * 2, min(dp[p3] * 3, dp[p5] * 5)) # 更新指向 # 注意这里不能只更新一个指针 # 比如 6，可以由 2 * 2 * 2 形成，也可以由 2 * 3 组成 if( dp[i] == dp[p2] * 2): p2 += 1 if( dp[i] == dp[p3] * 3): p3 += 1 if( dp[i] == dp[p5] * 5): p5 += 1 return dp[n - 1]

复杂度分析

时间复杂度： O(n)。生成一个丑数只需常量时间，所以生成n个丑数需要 O(n)。空间复杂度：O(n)。dp数组的长度为n。

参考：

字节跳动面到这道题，有的读者一脸懵逼，有的读者笑嘻嘻

2.2 优先队列(小顶堆)

利用优先队列有自动排序的功能

生成丑数的规律：如果已知丑数 ugly ，那么 ugly * 2，ugly * 3 和 ugly * 5 也都是丑数。

既然求第n小的丑数，可以采用最小堆来解决。每次弹出堆中最小的丑数，然后检查它分别乘以2、3和 5后的数是否生成过，如果是第一次生成，那么就放入堆中。第n个弹出的数即为第n小的丑数。

具体：每次取出队头元素，存入队头元素 *2、队头元素 *3、队头元素 *5 但注意，像12这个元素，可由 4 乘3得到，也可由6乘2得到，所以要注意去重

########################## 比较慢 ################################ # class Solution: # def nthUglyNumber(self, n: int) -> int: # c = set() # m = 1 # stack = [1] # d = [] # while len(d) < n: # m = min(stack) # stack.remove(m) # d.append(m) # if m * 2 not in c: # stack.append(m * 2) # c.add(m * 2) # if m * 3 not in c: # stack.append(m * 3) # c.add(m * 3) # if m * 5 not in c: # stack.append(m * 5) # c.add(m * 5) # return d[n - 1] ########################## 比较快 ################################ import heapq class Solution: def nthUglyNumber(self, n: int) -> int: heap = [] heapq.heappush(heap, 1) seen = set() seen.add(1) factors = [2, 3, 5] curr_ugly = 1 for _ in range(n): curr_ugly = heapq.heappop(heap) for f in factors: new_ugly = curr_ugly * f if new_ugly not in seen: seen.add(new_ugly) heapq.heappush(heap, new_ugly) return curr_ugly

复杂度分析

时间复杂度： O(nlog(n))。弹出每个最小值时，时间复杂度都为堆的高度，因此时间复杂度为O(nlog(n)) 。空间复杂度： O(n)。遍历n个丑数，并将每个丑数乘以 2、3 和 5 的结果存入堆中。堆和哈希表的元素个数都不会超过 n * 3。

参考：

LeetCode题解