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退役队伍

编辑：刘凯旋