# way 1 复杂度过高 class Solution: def GetUglyNumber_Solution(self, index): # write code here if index < 1: return None if index == 1: return index num = 2 index = index - 1 numcount = 0 final = [1] while index: print("------\nindex:\t", index) count = num print("count:\t", count) while ((count % 2 == 0) or (count % 3 == 0) or (count % 5 == 0)) and (count != 0): if count % 2 == 0: count = count // 2 if count % 3 == 0: count = count // 3 if count % 5 == 0: count = count // 5 if count == 1: index = index - 1 final.append(num) num = num + 1 else: num = num + 1 numcount += 1 print("numcount:\t", numcount) return num - 1, final # way 2 复杂度过高 class Solution: def GetUglyNumber_Solution(self, index): # write code here if index < 1: return None if index == 1: return 1 count = 1 def isUglyNumber(count): while count % 2 == 0: count = count // 2 while count % 3 == 0: count = count // 3 while count % 5 == 0: count = count // 5 if count == 1: return True else: return False num = 2 while True: if isUglyNumber(num): count += 1 if count == index: return num num += 1 # way 3 class Solution: def GetUglyNumber_Solution(self, index): # write code here if index < 1: return 0 uglylist = [1] twoPointer = 0 threePointer = 0 fivePointer = 0 count = 1 while count != index: minvalue = min(2*uglylist[twoPointer], 3*uglylist[threePointer], 5*uglylist[fivePointer]) uglylist.append(minvalue) count += 1 if minvalue == 2*uglylist[twoPointer]: twoPointer += 1 if minvalue == 3*uglylist[threePointer]: threePointer += 1 if minvalue == 5*uglylist[fivePointer]: fivePointer += 1 return uglylist[count - 1]