LeetCode 264. Ugly Number II.jpg

LeetCode 264. Ugly Number II

Description

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5.

Example:

Input: n = 10
Output: 12
Explanation: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.
Note:

1 is typically treated as an ugly number.
n does not exceed 1690.

描述

編寫一個程序，找出第 n 個丑數(shù)阔加。

丑數(shù)就是只包含質(zhì)因數(shù) 2, 3, 5 的正整數(shù)。

示例:

輸入: n = 10
輸出: 12
解釋: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 個丑數(shù)。
說明:

1 是丑數(shù)尊惰。
n 不超過1690。

思路

• 整型范圍內(nèi)(2^32)內(nèi)一共有1690個丑數(shù).
• 根據(jù)丑數(shù)的定義膀捷，num = 2^i * 3^j * 5^k.假設(shè)當(dāng)前的丑數(shù)是n全庸，下一個丑數(shù)num1一定是n*2，下二個丑數(shù)num2一定是n*3挑豌，n*5,num1*2 三個數(shù)中較小的一個.
• 丑數(shù)乘以2侯勉，或3铐拐，或5都是丑數(shù)，并且當(dāng)前的丑數(shù)一定會被乘以2虚青，乘以3，乘以5來產(chǎn)生新的丑數(shù)，只不過相乘所得到的結(jié)果并不是連續(xù)出現(xiàn)。比如當(dāng)前丑數(shù)是n宪赶，下一個丑數(shù)num1是n*2,再下一個丑數(shù)是num1*2辕棚，接下來才是n*3逝嚎。于是我們用i引几，j敞掘，k分別表示當(dāng)前丑數(shù)乘以2，3楣铁，5玖雁，并取所乘最小的丑數(shù)作為下一個丑數(shù)，然后剛才被選中的丑數(shù)向后移動一個.

# -*- coding: utf-8 -*-
# @Author:             何睿
# @Create Date:        2019-02-04 13:35:56
# @Last Modified by:   何睿
# @Last Modified time: 2019-02-04 14:25:45


class Solution:
    def nthUglyNumber(self, n):
        """
        :type n: int
        :rtype: int
        """
        uglynum = [1]
        # i:2的次數(shù)盖腕，j:3的次數(shù)赫冬，k：5的次數(shù)，count：丑數(shù)的個數(shù)
        # i表示當(dāng)前位置的丑數(shù)乘以2
        # j表示當(dāng)前位置的丑數(shù)乘以3
        # k表示當(dāng)前位置的丑數(shù)乘以5

        i, j, k, count = 0, 0, 0, 1
        while count < n:
            # 我們以對應(yīng)的上一個數(shù)為基底溃列，分別對應(yīng)乘上2劲厌，3，5哭廉，
            # 新的丑數(shù)一定是i脊僚，j，k位置的丑數(shù)對應(yīng)乘以2遵绰，3辽幌，5中的最小數(shù)
            uglyi, uglyj, uglyk = uglynum[i] * 2, uglynum[j] * 3, uglynum[k] * 5
            # 然后我們選擇最小的數(shù)
            uglynext = min(uglyi, uglyj, uglyk)
            # 如果uglynext == uglyi，說明當(dāng)前位置的丑數(shù)乘以2得到新的丑數(shù)
            # i自增一次表示用下一個數(shù)乘以2產(chǎn)生新的丑數(shù)
            if uglynext == uglyi: i += 1
            # 如果uglynext == uglyj椿访，說明當(dāng)前位置的丑數(shù)乘以3得到新的丑數(shù)
            # j自增一次表示用下一個數(shù)乘以3產(chǎn)生新的丑數(shù)
            if uglynext == uglyj: j += 1
            # 如果uglynext == uglyk乌企，說明當(dāng)前位置的丑數(shù)乘以5得到新的丑數(shù)
            # k自增一次表示用下一個數(shù)乘以5產(chǎn)生新的丑數(shù)
            if uglynext == uglyk: k += 1
            uglynum.append(uglynext)
            count += 1
        # 返回最后一個數(shù)字
        return uglynum[-1]

源代碼文件在這里.
?本文首發(fā)于何睿的博客，歡迎轉(zhuǎn)載成玫，轉(zhuǎn)載需保留文章來源加酵，作者信息和本聲明.