subject : To include only qualitative factors 2、3 and 5 The number of is called ugly (Ugly Number). for example 6、8 All ugly numbers , but 14 No , Because it contains quality factors 7. It's customary for us to 1 As the first ugly number . Seek the order from small to large N Ugly number .
analysis : Keep separately *2、*3、*5 The minimum position of , Number of times with this position *2、3、5 Compare separately , that will do .
Code :
class Solution:
def func(self , n):
if n == 0:
return 0
res = []
n2 , n3 , n5 = 0,0,0
for i in range(n):
if i == 0:
res.append(1)
else:
r2 , r3 , r5 = res[n2]*2 , res[n3]*3 , res[n5]*5
to_add = min(r2 , r3 , r5)
res.append(to_add)
if r2 == to_add:
n2 += 1
if r3 == to_add:
n3 += 1
if r5 == to_add:
n5 += 1
return res
a = 10
s = Solution()
print(s.func(a))
Output :
[1, 2, 3, 4, 5, 6, 8, 9, 10, 12]