python3 纯数学方法，好懂但是耗时长，好在空间复杂度低
寻找丑数
http://www.nowcoder.com/questionTerminal/cff52ae345a248ea94c8c0cc2d278474
时间复杂度应该是O(n)，但是多出了很多不必要的计算，不过空间复杂度只有O(1)。
n = int(input().strip())
count = 1
num = 1
num_copy = 1
while count < n:
num_copy += 1
num = num_copy
while num % 2 == 0:
num //= 2
while num % 3 == 0:
num //= 3
while num % 5 == 0:
num //= 5
if num == 1:
count += 1
print(num_copy)再上一个时间复杂度低的代码，它通过列表来存储出现的丑数，再用丑数来计算丑数，从而省掉了很多非丑数的计算。
n = int(input())
dp, a, b, c = [1] * n, 0, 0, 0
for i in range(1, n):
n2, n3, n5 = dp[a] * 2, dp[b] * 3, dp[c] * 5
dp[i] = min(n2, n3, n5)
if dp[i] == n2:
a += 1
if dp[i] == n3:
b += 1
if dp[i] == n5:
c += 1
print(dp[-1])
美的集团公司福利 742人发布
