难度: Medium
给你一个整数 n ，请你找出并返回第 n 个 丑数 。
丑数 就是质因子只包含 2、3 和 5 的正整数。
示例 1：
输入：n = 10 输出：12 解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。
示例 2：
输入：n = 1 输出：1 解释：1 通常被视为丑数。
提示：
1 <= n <= 1690
Submission
运行时间: 29 ms
内存: 16.0 MB
arr = [1]
i2 = i3 = i5 = 0
for i in range(1700):
a2 = arr[i2] * 2
while a2 <= arr[-1]:
i2 += 1
a2 = arr[i2] * 2
a3 = arr[i3] * 3
while a3 <= arr[-1]:
i3 += 1
a3 = arr[i3] * 3
a5 = arr[i5] * 5
while a5 <= arr[-1]:
i5 += 1
a5 = arr[i5] * 5
mn = min(a2, a3, a5)
arr.append(mn)
if mn == a2:
i2 += 1
elif mn == a3:
i3 += 1
else:
i5 += 1
print(arr[:51])
class Solution:
def nthUglyNumber(self, n: int) -> int:
return arr[n - 1]
Explain
该题解采用动态规划的思路，使用三个指针 i2、i3、i5 分别记录当前应该乘以 2、3、5 的丑数的下标。通过比较 arr[i2]*2、arr[i3]*3 和 arr[i5]*5 的大小，将最小的数添加到数组 arr 中，并递增对应的指针。最终返回 arr[n-1] 即为第 n 个丑数。
时间复杂度: O(n)
空间复杂度: O(n)
arr = [1]
# 初始化三个指针
i2 = i3 = i5 = 0
for i in range(1700):
# 计算当前应该乘以 2 的最小丑数
a2 = arr[i2] * 2
while a2 <= arr[-1]:
i2 += 1
a2 = arr[i2] * 2
# 计算当前应该乘以 3 的最小丑数
a3 = arr[i3] * 3
while a3 <= arr[-1]:
i3 += 1
a3 = arr[i3] * 3
# 计算当前应该乘以 5 的最小丑数
a5 = arr[i5] * 5
while a5 <= arr[-1]:
i5 += 1
a5 = arr[i5] * 5
# 将最小的丑数加入数组
mn = min(a2, a3, a5)
arr.append(mn)
# 递增对应的指针
if mn == a2:
i2 += 1
elif mn == a3:
i3 += 1
else:
i5 += 1
print(arr[:51])
class Solution:
def nthUglyNumber(self, n: int) -> int:
return arr[n - 1]
Explore
使用三个指针i2、i3、i5的目的是为了确保每次生成的丑数是按顺序递增的，同时避免重复计算和重复添加。如果每次简单地对数组中的每个元素乘以2、3、5，然后选择最小值，这会导致计算效率低（因为很多乘积是重复的），且可能会重复添加相同的丑数，打破丑数递增的顺序。使用指针可以精确地控制每个基数（2、3、5）乘以合适的前一个丑数，确保每次添加的丑数都是当前未出现过的最小丑数。
while循环确保指针i2、i3、i5总是指向尚未乘以2、3、5的最小丑数。在循环中，如果指针对应的乘积小于或等于当前数组中的最大丑数（arr[-1]），则表明这个乘积已经被添加过了或者不是下一个最小丑数，因此指针需要向前移动到下一个位置。这样，每个指针始终对应于还未被乘以其对应因子产生新丑数的位置，保证了丑数的正确顺序和唯一性。
通过同时比较三个不同指针（i2、i3、i5）对应的乘积（a2、a3、a5）并选取其中的最小值，题解中的方法可以避免重复。如果两个或三个乘积相等，只有其中的最小值被添加到数组中，而所有等于这个最小值的乘积对应的指针都会被递增。这样可以确保每个新添加的丑数都是唯一的，并且是当前尚未添加过的最小丑数。
该算法的时间复杂度主要取决于n的大小，因为每次迭代都涉及计算三个乘积并更新数组和指针。随着n的增大，数组和每次迭代的计算量也增加，但由于每次迭代只处理三个计算和一些比较操作，其时间复杂度为O(n)，空间复杂度也为O(n)，这在实际中通常是可接受的。但是，如果n非常大，例如接近整型上限，这种算法的内存使用量会成为一个瓶颈，因为它需要存储所有计算出的丑数。