算法第二十天-丑数Ⅱ

发布时间:2024年01月16日

丑数Ⅱ

题目要求

在这里插入图片描述

解题思路

题目的要求是让我们生成第n个丑数。如果考虑逐个遍历自然数是否为丑数,一定会超时。这里推荐使用生成的办法。
要生成第n个丑数,我们必须从第一个丑数1开始,向后逐渐的寻找。丑数只包含2,3,5三个因子,所以生成方式是在已经生成的丑数集合中乘以[2,3,5]而得到新的丑数。
现在的问题是在已经生成的丑数集合中,用哪个数字乘以2?用哪个数字乘以3?用哪个数字乘以5?
很显然的一个结论:用还没乘过2的最小丑数乘以2;用还没乘过3的最小丑数乘以3;用还没乘过5的最小丑数乘以5。然后在得到的数字中取最小,就是新的丑数。
实现的方法是用动态规划

  • 我们需要定义3个指针index2,index3,index5分别表示丑数集合中还没乘过2,3,5的丑数位置。
  • 然后每次新的丑数 dp[i]=min(dp[index2]*2,dp[index3]*3,dp[index5]*5)
  • 最后根据dp[i]是由index2,index3,index5中哪个相乘得到的,对应的把此index+1,表示还没乘过该index的最小丑数变大了。

代码

class Solution:
    def nthUglyNumber(self, n: int) -> int:
        if n < 0:
            return 0
        index2,index3,index5=0,0,0
        dp=[1] *n
        for i in range(1,n):
            dp[i]=min(2 * dp[index2],3 * dp[index3], 5 * dp[index5])
            if dp[i] == 2*dp[index2]: index2 +=1
            if dp[i] == 3*dp[index3]: index3 +=1
            if dp[i] == 5*dp[index5]: index5 +=1
        return dp[n-1]

复杂度分析

时间复杂度: O ( N ) O(N) O(N)
空间复杂度: O ( N ) O(N) O(N)

文章来源:https://blog.csdn.net/weixin_43186779/article/details/135635361
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。