面试题34:丑数

题目:我们把只包含因子2,3和5的数称作丑数。求按从小到大的顺序的第1500个丑数。例如6,8都是丑数,但14不是,因为它包含因子7.习惯上我们把1当做第一个丑数。


分析

最直观的方法是从1往后逐个判断每个数字,并设一个计数器。如果一个数是丑数,计数器加一。当计数器到1500时,输出这个数即可。但求一个数的所有因子的时间复杂度为O(n<sup>0.5</sup>)(对否?),总的时间复杂度为O(n<sup>1.5</sup>)。

更好的一种方法是以空间换时间,即创建一个数组保存已经找到的丑数,这样就不用重复计算前面已经计算过的。而是每次用数组中的一个数来计算出下一个丑数。一般我们会选择数组中2,3,5对应的最后一个数来计算下一个丑数,所以需要使数组是有序的。因此可以用3个变量T2,T3,T5来指示2,3,5对应的最后一个丑数,然后用着三个数分别乘以2,3和5得到R2,R3和R5。只需要将R2,R3,R5中的最小者放入数组中即可,并更新相应的T2,T3或T5。

代码如下:

Min(int a,int b,int c)
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
{
int min=a&gt;b?b:a;
min=min&gt;c?c:min;
return min;
}
int GetUglyNumber(int index)
{
if(index&lt;=0)
return 0;
vector&lt;int&gt; v;
v.push_back(1);
int M2=0,M3=0,M5=0;
while(v.size()&lt;index)
{
int min=Min(v[M2]*2,v[M3]*3,v[M5]*5);
v.push_back(min);
while(v[M2]*2&lt;=v[v.size()-1])
M2++;
while(v[M3]*3&lt;=v[v.size()-1])
M3++;
while(v[M5]*5&lt;=v[v.size()-1])
M5++;
}
return v[v.size()-1];
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

<div>来自为知笔记(Wiz)</div>