JZ49 丑数

发表于 分类于 本文字数： 357 阅读时长 ≈ 1 分钟

JZ49 丑数

描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第 n个丑数。

数据范围：$0≤n≤2000$

要求：空间复杂度 $O(n)$ ， 时间复杂度 $O(n)$

示例1

1
2
输入：7
返回值：8

题解

我的第一想法是打表

正解是使用三指针来生成下一个丑数，因为丑数一定是由$2^x3^y5^z$构成的，所以三个指针来追踪它们，然后逐个生成即可

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
# 三指针
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param index int整型 
# @return int整型
#
class Solution:
    def GetUglyNumber_Solution(self , index: int) -> int:
        if (index <= 6):
            return index
        res = []
        res.append(1)
        i2 = 0
        i3 = 0
        i5 = 0
        for i in range(index):
            res.append(min(res[i2]*2,min(res[i3]*3,res[i5]*5)))
            if(res[-1]==res[i2]*2):
                i2 += 1
            if(res[-1]==res[i3]*3):
                i3 += 1
            if(res[-1]==res[i5]*5):
                i5 += 1
        return res[index-1]

1
2
3
4
5
6
7
8
# 打表 但是我不确定怎么找到的30，20，15
# 看了评论区本人的回答，居然是试出来的...
# 打表是对的
def GetUglyNumber_Solution(self, index):
        res=[2**i*3**j*5**k  for i in range(30)  for j in range(20)   for k in range(15)]
        res.sort()
        return res[index-1] if index else 0