【劍指offer】醜數的查找 python

自己看了很久，沒有想出來，借鑒了下其他人分享的思路，總算是了解了。

題目：把隻包含質因子2、3和5的數稱作醜數（Ugly Number）。例如6、8都是醜數，但14不是，因為它包含質因子7。 習慣上我們把1當做是第一個醜數。求按從小到大的順序的第N個醜數。

思路

這裡主要有兩條思路：

1、按照順序依次判斷整數是否為醜數，條件（因子隻有2，3，5），這種方法費時比較長，不是首選；

2、依照醜數的定義，按順序求出下一個醜數。這裡主要展示這種方法的代碼。

這裡的思路主要是要将醜數看作是現有2，3，5倍，既然都是2，3，5的倍數，那麼分别為2，3，5建立倍數索引，如果下一個醜數剛好是某個醜數的2倍，那對應倍數索引＋1，再次尋找最小值時，其備選項将變為為新醜數的2倍，

這裡要注意2 * 3，3 * 2這類存在相同的值，是以需要逐一驗證，不可直接跳出循環。

import time


def GetUglyNumber_Solution(index):

    """除1外，醜數主要來源于現有醜數的2， 3， 5倍，"""

    if index <= 0:
        return 0
    if index == 1:
        return 1
    ugly_lists = [1]

    # 為2，3，5建立倍數索引，
    i_2, i_3, i_5 = 0, 0, 0
    for i in range(1, index):

        # 下一個醜數來源于未加入的2， 3，5倍數值的最小值
        new_ugly = min([ugly_lists[i_2] * 2, 
        				ugly_lists[i_3] * 3, ugly_lists[i_5] * 5])
        ugly_lists.append(new_ugly)

        # 找到最小值來源于2， 3， 5中的哪個倍數值，對應索引值＋1，
        # 這裡要注意2*3，3*2這類存在相同的值，是以需要逐一驗證，不可直接跳出循環。
        if ugly_lists[i] == ugly_lists[i_2] * 2:
            i_2 += 1
        if ugly_lists[i] == ugly_lists[i_3] * 3:
            i_3 += 1
        if ugly_lists[i] == ugly_lists[i_5] * 5:
            i_5 += 1

    return ugly_lists[-1]


if __name__ == '__main__':

    for i in range(10):
        print(GetUglyNumber_Solution(i))

    t = time.clock()
    print(GetUglyNumber_Solution(1000))
    print("運作時間：", time.clock())
           

運作結果如下：

參考：

醜數–python實作：https://blog.csdn.net/waterkong/article/details/78154611；

[劍指Offer]醜數[Python] ：https://blog.csdn.net/Jillian_sea/article/details/80380275； （ps 這個講的很詳細呢)