丑数：最直观的想法是，暴力质因数分解，由于此处质因子只有2、3、5，故与原始质因数分解写法有些许不同。首先编写isUgly函数用于判断数n是否为丑数，由于1、2、3、4、5、6均是丑数，故若index小于等于6，则直接返回index即可，反之记录当前丑数数量num为6，再从7开始遍历，如果当前数是丑数，则对应丑数数量num加一，再判断丑数数量num是否等于给定个数index，如果是则记录结果并返回。(超时)

//判断是否为丑数 与原始的质因数分解不同
bool isUgly(int n)
{
   while(n%2==0) n/=2;
   while(n%3==0) n/=3;
   while(n%5==0) n/=5;
   return n==1;
}
int GetUglyNumber_Solution(int index) 
{
   // 1 2 3 4 5 6均是丑数
   if(index<=6)
      return index;
   //记录第一个丑数
   int num=6; 
   //记录对应结果
   int result;
   for(int i=7;;i++)
   {
       //如果是丑数则丑数数量加一
       if(isUgly(i))
         num++;
       //如果数量等于待求解的则记录结果
       if(num==index)
       {
           result=i;
           break;
       }
   }
   return result;
}

优化：上述方法很明显超时，故我们需要找出方法对其进行优化。由于质因子只有2、3、5的为丑数，且所需的n个丑数是按从小到大的顺序进行排列的，假设我们知道前n-1个丑数，那么我们只需将前n-1个丑数每一个分别乘以2、3、5即可得到新的丑数，然后从中检查出与前n-1个丑数不重复的且最小的丑数即可得到第n个丑数。但是这样做法下的时间复杂度仍然很高，所以我们继续想办法优化。根据规律可以知道，第一个丑数为1，将其分别乘以2、3、5，然后取最小的2，由于2是由1乘以2得到的，所以下一个因为乘以2得到的丑数必然是根据2得到的，这时我们就可以根据此单调性规律来设置三指针。具体做法如下：使用res[i]表示第i个丑数，其中第一个丑数是1，分别使用指针p2、p3、p5表示下一个丑数可以根据res[p2]*2、res[p3]*3、res[p5]*5得到，首先根据三指针得到最小的丑数，然后判断该丑数是由哪一个得到的，并将对应的指针后移，当数组长度小于index时一直执行直至相等，最后返回res最后一个元素即可。

int GetUglyNumber_Solution(int index) 
{
    // 1 2 3 4 5 6均是丑数
    if(index<=6)
       return index;
    //用于记录丑数
    vector<int> res;
    //用于记录最小值
    int minx;
    //第一个丑数为1
    res.push_back(1);
    //三指针 分别标记下一个丑数可以根据 res[i]*2 res[j]*3 res[k]*5得到
    int p2=0,p3=0,p5=0;
    //当数组长度小于index一直执行直至相等
    while(res.size()<index)
    {
        //取最小值
        minx=min({res[p2]*2,res[p3]*3,res[p5]*5});
        res.push_back(minx);
        if(minx==res[p2]*2)
           p2++;
        if(minx==res[p3]*3)
           p3++;
        if(minx==res[p5]*5)
           p5++;
    }
    return res[res.size()-1];
}