面试49：丑数

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

思路跟书上一样：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if (index <= 0)
            return 0;
        //因为丑数的前5个数是1,2,3,4,5,所以可直接返回
        if (index > 0 && index <= 5)
            return index;
        vector<int> sequenceUgly = { 1,2,3,4,5 };
        return getUglyNumber(sequenceUgly, index);
    }
    //递归获得有序丑数数组
    int getUglyNumber(vector<int>& sequenceUgly, int index)
    {
        int uglySize = sequenceUgly.size();
        //若丑数数列达到要求长度，停止递归，返回尾部值即为所求
        if (uglySize == index)
            return sequenceUgly[uglySize - 1];
        //M是原丑数数列中最大的一个数
        int M = sequenceUgly[uglySize - 1];
        //M2s是丑数数列乘以2之后，第一个大于M的数,M3,M5同理
        int M2 = getMax(sequenceUgly, 2, M);
        int M3 = getMax(sequenceUgly, 3, M);
        int M5 = getMax(sequenceUgly, 5, M);
        //求出M2,M3,M5中最小的一个数
        int minM = min(M2, M3);
        if (minM > M5)
            minM = M5;
        sequenceUgly.push_back(minM);
        //cout << "minM: " << minM << endl;
        return getUglyNumber(sequenceUgly, index);
    }

    //丑数数列中的数乘以data(2/3/5)后，挑选出大于M的第一个数返回
    int getMax(vector<int>& sequenceUgly, int data, int M)
    {
        vector<int> duplicateUgly(sequenceUgly);
        for (int i = 0; i < duplicateUgly.size(); ++i)
        {
            duplicateUgly[i] = duplicateUgly[i] * data;
        }
        int j = 0;
        while (j<duplicateUgly.size()&&duplicateUgly[j]<=M)
        {
            ++j;
        }
        return duplicateUgly[j];
    }
};

这里没有用那种逐个判断每个整数是否是丑数的方法，但还是贴上判断整数n是否为丑数的代码：

bool isUgly(int n)
{
    while (n % 2 == 0)
        n = n / 2;
    while (n % 3 == 0)
        n = n / 3;
    while (n % 5 == 0)
        n = n / 5;
    return (n == 1) ? true : false;
}