leetcode刷题指南之UglyNumberII

题目分析

编程找到第个。

的定义:

正整数

只由3个素数因子组成:

例如,是前个。一般被定义为。

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

解题思路(1)

从开始判断每一个数字是否是,直到找到第个。

判断一个数字是否是,可以由以下的程序实现:

boolisUgly(intnum)

{if(num

returnfalse;

while(num%2==) num/=2;

while(num%3==) num/=3;

while(num%5==) num/=5;

returnnum==1;}

判断一个数字是否是,时间复杂度大致为,假如第个是,时间开销还是比较大的,在Online Judge上测试,超时。

解题思路(2)

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

1. 若一个数字是,他一定能被除尽。

2.,做除法,我们反推除法过程。

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

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

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

1. 第一个是,由生成的数字是。

2. 所以第二个是,由生成的数字是。

3. 我们发现第三个是,而是第四个。

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

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

1.表示第个。

2. 设置三个指针,分别指向三个数字当前应该乘以哪个。

3.三个中最小的一个,就是下一个。

4. 这个要生成的如果等于中的某几个,那么对应的就要加一,也就是指向下一个要乘以的。

通过这种控制方式

保证了生成的顺序

不会重复生成同一个。

不会遗漏任何。

算法复杂度:时间复杂度是,空间复杂度也是

代码示例

作者:东大ACM退役队伍

编辑:刘凯旋

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181024B00YCR00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券