题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。

例如 6、8 都是丑数，但 14 不是，因为它包含质因子 7。

求第 n 个丑数的值。

样例
输入：5

输出：5
注意：习惯上我们把 1 当做第一个丑数。

算法1

(暴力枚举) $O(n)$

丑数序列 可以看作是2 3 5的倍数最后归并成的一个序列，去掉重复的元素

把每一个数2 3 5 的倍数按照大小顺序加进来

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        if(n == 1) return 1;
        int i = 0, j = 0, k = 0;  //i j k 3个因子，
        vector<int> num(1,1);

        while(num.size() < n){
            int min_num = min(num[i] * 2, min(num[j] * 3, num[k] * 5));   //找出3因子与对应数乘积的最小值
            num.push_back(min_num);
            if(num[i] * 2 == min_num) ++i;  //过滤掉相同的元素
            if(num[j] * 3 == min_num) ++j;
            if(num[k] * 5 == min_num) ++k;
        }
        return num[n - 1];

    }
};