剣指offer面接問題49 python版+解析:ブス数

844 ワード

タイトルの説明
素因数2,3,5のみを含む数をブス数(Ugly Number)と呼ぶ.例えば、6、8はすべて醜数であるが、14は質量因子7を含むためではない.習慣的に私たちは1を最初の醜数と見なしています.小さいから大きい順のN番目の丑数を求めます.
 
構想:配列を定義し、中にはソートされた醜い数があります.我々は既存の最大丑数にそれぞれ2,3,5を乗じて、得られた3つの数の中の最小数は次の丑数である.
# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index<=0:
            return 0
        
        UglyList = [1]
        index2 = 0
        index3 = 0
        index5 = 0
        for i in range(index-1):
            newUgly = min(UglyList[index2]*2, UglyList[index3]*3, UglyList[index5]*5)
            UglyList.append(newUgly)
            if newUgly%2==0:
                index2+=1
            if newUgly%3 == 0:
                index3+=1
            if newUgly%5 == 0:
                index5+=1
        return UglyList[-1]