丑数

将查找的丑数按从小到大的顺序排好序，注意每个丑数毕为前面的丑数乘以2、3或5得到的；把现有最大丑数记为M，则把第一个乘以2后大于M的结果记为M2，同理，把每个丑数乘以3和5 ，得到的第一个大于M的结果为M3和M5，那么下一个丑数必为M2/M3/M5这三个数的最小者。

辅助空间

vector:用vector存储按序生成的丑

辅助变量

t2：t2位置之前的丑数*2之后 ≤ 最大丑数，t2位置的丑数*2之后 > 最大丑数

t3：t3位置之前的丑数*3之后 ≤ 最大丑数，t3位置的丑数*3之后 > 最大丑数

t5：t5位置之前的丑数*5之后 ≤ 最大丑数，t5位置的丑数*5之后 > 最大丑

按序计算丑数

按序计算最大丑数

最大丑数 = min(vec[t2]*2,vec[t3]*3,vec[t5]*5)

更新三个辅助变量

当vec[t2]*2 == 最大丑数时，证明最大丑数 = t2位置的丑数 * 2，不满足t2的定义。

当vec[t3]*3 == 最大丑数时，证明最大丑数 = t3位置的丑数 * 3，不满足t3的定义。

当vec[t5]*5 == 最大丑数时，证明最大丑数 = t5位置的丑数 * 5，不满足t5的定义。

 1 class Solution {
 2 public:
 3     int GetUglyNumber_Solution(int index) {
 4         if(index==0) return 0;
 5         if(index==1) return 1;
 6         vector<int> res(index,1);
 7         int t2=0,t3=0,t5=0;
 8         for(int i=1;i<index;i++){
 9             res[i] = min(res[t2]*2,min(res[t3]*3,res[t5]*5));
10             if(res[i]==res[t2]*2) t2++;
11             if(res[i]==res[t3]*3) t3++;
12             if(res[i]==res[t5]*5) t5++;
13         }
14         return res[index-1];
15     }
16 };