丑数（数学，二分）

描述

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

示例1

输入：

7

复制返回值：

8

思路：丑数必定是由若干个2，3，5相乘获得的，每个丑数乘2.3.5分别可以衍生出3个新丑数，但是会存在重复。所以定义三个指针分别代表乘2.3.5。开始都指向0，每次乘2.3.5，最小的值就是下一个丑数，那相应的指针也得++。在动态的比较中获得最小的丑数。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
    int* result = new int[index];
    int p2 = 0,p3 = 0,p5 = 0;
    result[0] = 1;
    for(int i = 1;i < index;i++)
    {
        int min1 = min(result[p2]*2,min(result[p3]*3,result[p5]*5));
        if(min1 == result[p2]*2)
        {
            result[i] = min1;
            p2++;
        }
        if(min1 == result[p3]*3)
        {
            result[i] = min1;
            p3++;
        }
        if(min1 == result[p5]*5)
        {
            result[i] = min1;
            p5++;
        }
    }
        return result[index-1];
    }
};