leetcode刷题指南之UglyNumberII

关注文章

题目分析

编程找到第nugly number
ugly number的定义:

  • 正整数

  • 只由3个素数因子组成:2, 3, 5


例如,1, 2, 3, 4, 5, 6, 8, 9, 10(2*5), 12(2*2*3)是前10ugly number一般1被定义为ugly number

11不是一个ugly number,因为11由素数11组成。















解题思路(1)


1开始判断每一个数字是否是ugly number,直到找到第nugly number
判断一个数字是否是
ugly number,可以由以下的程序实现:

bool isUgly(int num) 
{if(num<=0)
            return false;
while(num%2==0) num/=2;
while(num%3==0) num/=3;
while(num%5==0) num/=5;
return num==1;}


判断一个数字是否是ugly number,时间复杂度大致为O(log(num)),假如第nugly numbernum,时间开销还是比较大的,在Online Judge上测试,超时。




解题思路(2)

由判断一个数字是否是ugly number的程序,我们可以得到一点启发:

1.  若一个数字是ugly number,他一定能被2, 3, 5除尽。


2.  num=12,做除法12/2=6, 6/2=3, 3/3=1,我们反推除法过程1*3=3, 3*2=6, 6*2=12


3.  换句话,每一个ugly number都可以通过反复地乘以2, 3, 5得到。


既然是反复地做乘法,那就是递推的过程,也就是说,可以通过已有那些的ugly number,得到之后的ugly number,这是一种生成数字的过程,比判别数字是否是ugly number快了许多。

我们希望顺序地生成ugly number,当生成到第nugly number,就完成了任务。

1.  第一个ugly number1,由1生成的数字是2, 3, 5

2.  所以第二个ugly number2,由2生成的数字是4, 6, 10

3.  我们发现第三个ugly number3,而4是第四个ugly number


可见,想要顺序地生成ugly number,我们还要精心设计一下控制顺序的方法。


要生成接下来的
ugly number,之前的那些ugly number中的每一个都要乘以2, 3, 5,我们只要保证每一个ugly number都乘过这三个数即可。

1.  dp[i]表示第i+1ugly number

2.  设置三个指针index_2, index_3, index_5,分别指向2, 3, 5三个数字当前应该乘以哪个ugly number


3.  2*dp[index_2], 3*dp[index_3], 5*[index_5]三个ugly number中最小的一个,就是下一个ugly number


4.  这个要生成的ugly number如果等于2*dp[index_2], 3*dp[index_3],  5*[index_5]中的某几个,那么对应的index_x就要加一,也就是指向下一个要乘以xugly number


通过这种控制方式

  • 保证了生成ugly number的顺序

  • 不会重复生成同一个ugly number

  • 不会遗漏任何ugly number


算法复杂度:时间复杂度是O(n),空间复杂度也是O(n)




 代码示例 


 1class Solution {
2public:
3int nthUglyNumber(int n) {
4    if(n<=0return 0;
5    vector<int> dp(n);
6    dp[0]=1;
7    int index_2=0, index_3=0, index_5=0;
8    for(int i=1; i<n; i++){
9        dp[i]=min(dp[index_2]*2, min(dp[index_3]*3, dp[index_5]*5));
10        if(dp[i]==dp[index_2]*2) index_2++;
11        if(dp[i]==dp[index_3]*3) index_3++;
12        if(dp[i]==dp[index_5]*5) index_5++;
13    }
14    return dp[n-1];
15}
16};


作者:东大ACM退役队伍

编辑:刘凯旋


东大ACM退役队伍

赞赏

 人赞赏

长按二维码向我转账

受苹果公司新规定影响,微信 iOS 版的赞赏功能被关闭,可通过二维码转账支持公众号。

文章转载自公众号

编程与算法之美
    阅读

    微信扫一扫
    关注该公众号

    文章被以下专辑收录
    3844
    {{panelTitle}}
    支持Markdown和数学公式,公式格式:\\(...\\)或\\[...\\]

    还没有内容

    关注微信公众号