面试题34：丑数

题目：我们把只包含因子2、3和5的数称作丑数。求从小到大的顺序的第1500个丑数。例如6和8是丑数，但14不是。习惯上我们

把1当做第一个丑数。

解法：创建数组保存已经找到的丑数，用空间换时间

创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2、3或者5得到的。

 1 int getUglyNumber(int index)
 2 {
 3     if (index <=0)
 4         return 0;
 5     vector<int>v;
 6     v.push_back(1);
 7     int p2=0,p3=0,p5=0;
 8     while (v.size()!=index)
 9     {
10         int temp_P2 = v[p2]*2;
11         int temp_P3 = v[p3]*3;
12         int temp_P5 = v[p5]*5;
13         int temp = (temp_P2 < temp_P3)?temp_P2:temp_P3;
14         temp = (temp < temp_P5)?temp:temp_P5;
15         v.push_back(temp);
16         while (v[p2]*2 <= temp)
17             ++p2;
18         while (v[p3]*3 <= temp)
19             ++p3;
20         while (v[p5]*5 <= temp)
21             ++p5;
22     }
23     return v[v.size()-1];
24 }

PS：重点在于理解3个while循环，因为temp为已经找到的最大丑数，下一个丑数必定大于temp，而下一个丑数是由前面的丑数乘以2、3和5得到的，因此，需要将p2,p3和p5移动到指向大于temp的丑数，再从中选出最小的丑数作为下一个丑数。