Leetcode 264. 丑数 II

题目描述

编写一个程序，找出第 n 个丑数。

丑数就是只包含质因数 2, 3, 5 的正整数。

示例 1:

输入: n = 10

输出: 12

解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明

• 1 是丑数。
• n 不超过1690。

解法

丑数只包含质因数 2,3,5，即丑数由 2,3,5 与其他丑数相乘获得。因此可以维持一个递增丑数列表，将丑数列表中元素与 2,3,5 相乘的最小值作为新元素放入列表，直到获得第 n 个丑数。

可以给 2,3,5 三个数分别分配一个列表下标，在 2,3,5 与对应下标的元素相乘中选择最小值添加进列表，并修改下标指针，则可以依次获得丑数。

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        arr,two,three,five=[1],0,0,0
        for i in range(n-1):
            tmp=min(arr[two]*2,arr[three]*3,arr[five]*5)
            arr.append(tmp)
            if arr[two]*2==tmp:
                two+=1
            if arr[three]*3==tmp:
                three+=1
            if arr[five]*5==tmp:
                five+=1                
        return arr[-1]

可能存在相乘后数值相等的情况，所以判断是否同时修改下标。