LeetCode Python n番目のブス数

一つ一つ探す方法は,効率が比較的低い.

def findKthUgly(k):
    count = 0
    n = 1
    while True:
        if isUgly(n):
            count += 1
        if count == k:
            return n
        else:
            n += 1


def isUgly(number):
    while number%2 == 0:
        number = number/2
    while number%3 == 0:
        number = number/3
    while number%5 == 0:
        number == number/5
    if number == 1:
        return True
    else:
        return False

もう1つのアルゴリズムは丑数から*2,*3,*5を計算して後の丑数を計算し、競争するたびに最小の値を丑数リストに追加する.ただ、現在のlistの中で最大の丑数より大きい最初の丑数を見つける方法を考えなければならない.index 2,index 3,index 5を利用して各数*2,*3,*5をlistに追加し、ugly[index 2]*2をlistに追加すればindex 2を次の丑数に指向する.このように推す.

def findKthUgly(k):
    ugly = []
    ugly.append(1)
    index = 1
    index2 = 0
    index3 = 0
    index5 = 0
    while index < k:
        val = min(ugly[index2]*2, ugly[index3]*3, ugly[index5]*5)
        if ugly[index2]*2 == val:
            index2 += 1
        if ugly[index3]*3 == val:
            index3 += 1
        if ugly[index5]*5 == val:
            index5 += 1
        ugly.append(val)
        index += 1
    return ugly[-1]