题解 | #丑数#

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

方法一 ：数学 枚举

丑数是只包含质因子2、3和5的数，可以从小到大枚举满足条件的数

先将满足条件的最小的数加入数组存储

直到第N个数。

图解：

复杂度分析

时间复杂度：O(N)，N为第N个数，遍历枚举；

空间复杂度：O(N)，存储与读取数据。

代码：

class Solution {
public:
    int GetUglyNumber_Solution(int index) {
        if(index==0)return 0;
        int x2=0,x3=0,x5=0;//丑数的因子只有2,3,5
        vector<int>res;
        res.push_back(1);
        for(int i=1;i<index;i++){
            res.push_back(min(res[x2]*2,min(res[x3]*3, res[x5]*5)));//将满足条件的最小丑数加入
            if(res[i]==res[x2]*2)x2++;//若满足条件则增加系数
            if(res[i]==res[x3]*3)x3++;
            if(res[i]==res[x5]*5)x5++;
        }
        return res[index-1];//返回第k个数
    }
};