面试题34：丑数

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

分析

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

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

代码如下：

```int Min(int a,int b,int c) { int min=a>b?b:a; min=min>c?c:min; return min; }

int GetUglyNumber(int index) { if(index<=0) return 0; vector v; v.pushback(1); int M2=0,M3=0,M5=0; while(v.size()<index) { int min=Min(v[M2]2,v[M3]3,v[M5]*5); v.pushback(min); while(v[M2]2<=v[v.size()-1]) M2++; while(v[M3]3<=v[v.size()-1]) M3++; while(v[M5]*5<=v[v.size()-1]) M5++; } return v[v.size()-1]; } ```

以上

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

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