劍指offer：丑數

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

# -*- coding: utf-8 -*-
# @Time         : 2019-07-11 23:24
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : getUglyNumber.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

class Solution:
    """
    題目中丑數的定義是只包含因子2,3,5的數，特別地，1是第一個丑數。

    解法1：
    從1開始，逐個判斷每個數字是不是丑數，如果是，則計數器加一，直到找到所要求的第n個丑數為止。
    但是這樣做的話會對很多非丑數進行計算，時間復雜度太高。

    解法2：
    定義一個數組，用于按順序保存已經找到的丑數，再定義三個指針p2, p3, p5，其中p2指向數組中第一個
    乘以2之后會比當前數組中末尾元素要大的數字；p3和p5同理。這樣，當p2 * 2之后就會比當前最后一個
    丑數要大，而當p3 * 3 之后也會比最后一個丑數要大， p5同理。這樣，當前最后一個丑數之后的第一個
    丑數就出現在p2 * 2, p3 * 3, p5 * 5之間，我們只需要比較這三個數的大小即可找到下一個丑數。
    注意每找到一個這樣的丑數之后我們就要更新p2, p3, p5，直到我們找到足夠多的丑數。
    這種方法是以空間換時間，我們維護了一個長度為n的數組，并最終返回這個數組的末尾元素。
    """
    def GetUglyNumber_Solution(self, index):
        if index <= 0:
            return 0

        uglyNumbers = [1] * index  # 用于保存已找到丑數的數組
        p2 = p3 = p5 = 0
        idx = 1

        while idx < index:
            # 每次都這三個數中找一個最小的作為下一個丑數
            nextUglyNumber = min(uglyNumbers[p2] * 2,
                                 uglyNumbers[p3] * 3,
                                 uglyNumbers[p5] * 5)
            uglyNumbers[idx] = nextUglyNumber

            # 然后更新這三個指針
            while uglyNumbers[p2] * 2 <= nextUglyNumber:
                p2 += 1
            while uglyNumbers[p3] * 3 <= nextUglyNumber:
                p3 += 1
            while uglyNumbers[p5] * 5 <= nextUglyNumber:
                p5 += 1

            idx += 1

        return uglyNumbers[index - 1]

def main():
    solution = Solution()
    index = 1
    print(solution.GetUglyNumber_Solution(index))

if __name__ == '__main__':
    main()