題目描述
把只包含質(zhì)因子2、3和5的數(shù)稱(chēng)作丑數(shù)（Ugly Number）。例如6、8都是丑數(shù)，但14不是，因?yàn)樗|(zhì)因子7。 習(xí)慣上我們把1當(dāng)做是第一個(gè)丑數(shù)。求按從小到大的順序的第N個(gè)丑數(shù)。

定制設(shè)計(jì)可以根據(jù)自己的需求進(jìn)行定制，成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站構(gòu)思過(guò)程中功能建設(shè)理應(yīng)排到主要部位公司成都網(wǎng)站設(shè)計(jì)、做網(wǎng)站的運(yùn)用實(shí)際效果公司網(wǎng)站制作網(wǎng)站建立與制做的實(shí)際意義

# -*- 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:
    """
    題目中丑數(shù)的定義是只包含因子2,3,5的數(shù)，特別地，1是第一個(gè)丑數(shù)。

    解法1：
    從1開(kāi)始，逐個(gè)判斷每個(gè)數(shù)字是不是丑數(shù)，如果是，則計(jì)數(shù)器加一，直到找到所要求的第n個(gè)丑數(shù)為止。
    但是這樣做的話會(huì)對(duì)很多非丑數(shù)進(jìn)行計(jì)算，時(shí)間復(fù)雜度太高。

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

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

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

            # 然后更新這三個(gè)指針
            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()