逐个判断每个整数是不是丑数的做法很直观但并不高效。首先我们来分析一下如何判断一个数是不是丑数，所谓一个数m是另一个数n的因子，是指n能被m整除，也就是n % m == 0。根据丑数的定义，丑数只能被2、3、5整除。也就是说，如果一个数能被2整除，就连续除以2；如果能被3整除，就连续除以3；如果能被5整除，就连续除以5。如果最后得到的是1，那么这个数就是丑数，否则不是。因此我们可以写出isUgly函数来判断一个数是不是丑数。接下来只要按照顺序判断每个整数是不是丑数。该实现如1所示，时间复杂度非常高是O（N^2），空间复杂度是O（N）。
上述的思路最大的问题就是需要计算每一个整数，即使一个数字不是丑数，我们还是需要对它执行求余数和除法操作，因此该算法的时间效率不是很高。接下去我们考虑用一个数组保存已经找到的丑数，用空间换时间的解法。这种思路的关键是在于怎样确保数组里面的丑数是排好序的。假设数组中已经有若干个排好序的丑数，并且把已有的最大的丑数记作M，接下来分析如果生成下一个丑数。该丑数肯定是前面某一个丑数乘以2、3或5的结果，所以我们优先考虑把已有的每个丑数乘以2。在乘2的时候，能得到若干个小于或等于M的结果。由于是按照顺序生成的，小于或等于M肯定已经在数组中了，我们不需要再次考虑；另外还会得到若干个大于M的结果，但我们只需要一个大于M的结果，因为我们希望丑数是按从小到大的顺序生成的，其他更大的结果等以后再说。我们把得到第一个乘2后大于M的结果记为M2，同样，我们把已有的每个丑数乘以3和5，能得到第一个大于M的结果M3和M5.那么下一个丑数应该是M2，M3和M5这三个数的最小者。
在前面分析的时候提到把已有的每个丑数分别乘以2、3和5，事实上这不是必需的，因为已有的丑数是按照顺序存在数组中的。对于乘以2而言，肯定存在一个某一个丑数T2，排在它之前的每个丑数乘以2得到的结果都会小于已有的最大的丑数，在它之后的每个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每个乘以2得到的结果都会太大。我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候去更新这个T2即可。对于乘以3和5而言，也存在同样的T3和T5。我们在方法2中展示了这种实现。这样做的时间复杂度为O（N），空间复杂度也为O（N）。
class Solution:
def nthUglyNumber1(self, n: int) -> int:
if n <= 0:
return 0
num = 0
uglyFound = 0
while uglyFound < n:
num += 1
if self.isUgly(num):
uglyFound += 1
return num
def isUgly(self, n):
while n % 2 == 0:
n //= 2
while n % 3 == 0:
n //= 3
while n % 5 == 0:
n //= 5
return n == 1
def nthUglyNumber2(self, n):
res, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
m2, m3, m5 = res[a] * 2, res[b] * 3, res[c] * 5
res[i] = min(m2, m3, m5)
if m2 == res[i]: a += 1
if m3 == res[i]: b += 1
if m5 == res[i]: c += 1
return res[-1]