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

公司主營業(yè)務(wù)：成都網(wǎng)站制作、成都網(wǎng)站建設(shè)、外貿(mào)營銷網(wǎng)站建設(shè)、移動(dòng)網(wǎng)站開發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競爭能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對我們的高要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。成都創(chuàng)新互聯(lián)推出兩當(dāng)免費(fèi)做網(wǎng)站回饋大家。

# -*- 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開始，逐個(gè)判斷每個(gè)數(shù)字是不是丑數(shù)，如果是，則計(jì)數(shù)器加一，直到找到所要求的第n個(gè)丑數(shù)為止。
    但是這樣做的話會對很多非丑數(shù)進(jìn)行計(jì)算，時(shí)間復(fù)雜度太高。

    解法2：
    定義一個(gè)數(shù)組，用于按順序保存已經(jīng)找到的丑數(shù)，再定義三個(gè)指針p2, p3, p5，其中p2指向數(shù)組中第一個(gè)
    乘以2之后會比當(dāng)前數(shù)組中末尾元素要大的數(shù)字；p3和p5同理。這樣，當(dāng)p2 * 2之后就會比當(dāng)前最后一個(gè)
    丑數(shù)要大，而當(dāng)p3 * 3 之后也會比最后一個(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è)長度為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()

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時(shí)售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價(jià)比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

文章標(biāo)題：劍指offer：丑數(shù)-創(chuàng)新互聯(lián)
文章分享：http://jinyejixie.com/article42/diegec.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供品牌網(wǎng)站建設(shè)、定制網(wǎng)站、域名注冊、靜態(tài)網(wǎng)站、用戶體驗(yàn)、自適應(yīng)網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)