丑数

---

---

题目描述

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

解题思路

根据丑数定义，说明丑数只能被2、3、5整除。同时也说明，若已知前面的丑数，乘2、3或5就可以得到之后的丑数。

例如存在一个乘 2 得到的丑数 T2，排在它之前的每一个丑数乘 2 后都不会 大于当前最大丑数。同样还存在乘3的T3，乘5的T5。

代码

class Solution
{
public:
    int GetUglyNumber_Solution(int index)
    {
        if (index < 7) // 因为 1，2，3，4，5，6都是丑数
            return index;
        vector<int> res(index); // ???
        for (int i = 0; i < 6; i++)
            res[i] = i + 1;
        int t2 = 3, t3 = 2, t5 = 1; // 在前6个丑数中，满足乘相应因子不大于最大丑数6的最大数组下标
        for (int i = 6; i < index; i++)
        {
            res[i] =min(res[t2] * 2,min(res[t3] * 3, res[t5] * 5));
            while (res[i] >= res[t2] * 2)
                t2++;
            while (res[i] >= res[t3] * 3)
                t3++;
            while (res[i] >= res[t5] * 5)
                t5++;
        }
        return res[index-1];
    }
};

参考博文链接：https://cuijiahua.com/blog/2018/01/basis_33.html