丑数

题目描述

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

思路

由于丑数的性质，所有的丑数都是前面某一个数字2，3或5倍。找到前面n-1个丑数乘上2，3，5某个数，刚好大于第n-1个丑数的那个数字即为第n个丑数。
t2,t3,t5记录队列中三个队列最小值的编号。如果队列中t2,t3,t5三个编号2，3，*5的值为最小值，则对应的ti+1，否则不更新ti的值。

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        vector<int>result;
        result.push_back(1);
        int t2=0,t3=0,t5=0;
        for (int i = 1; i <index; i++)
        {
            result.push_back(min(result[t2]*2,min((result[t3]*3),result[t5]*5)));
            if (result[i] == result[t2] * 2) {
                t2++;
            }
            if (result[i] == result[t3] * 3) {
                t3++;
            }
            if (result[i] == result[t5] * 5) {
                t5++;
            }
        }
        return result[index - 1];
    }
};