题目描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

  1. class Solution:
  2.     def GetUglyNumber_Solution(self, index):
  3.         # write code here
  4.         if index == 0:
  5.             return 0
  6.         dp = [0] * index
  7.         dp[0] = 1
  8.         a,b,c = 0,0,0
  9.         for i in range(1,index):
  10.             n2,n3,n5 = dp[a]*2,dp[b]*3,dp[c]*5
  11.             dp[i] = min(n2,n3,n5)
  12.             if dp[i] == n2: a+=1
  13.             if dp[i] == n3: b+=1
  14.             if dp[i] == n5: c+=1
  15.         return dp[index-1]