题目描述

丑数，这题可以理解为求取只包含2，3，5质数因为的数的从小到大的集合，可以考虑为一个三路归并的问题，第一路是包含质因子2的所有数的集合，第二路是包含3的质因子的所有数的集合，同理，第三路是包含5的质因子的所有数的集合，但是可以看出，这三路是有交集的，所以需要去重，还有就是需要指出的是此为只包含2,3,5质因子的集合。就yxcls所说的题解来看，可以看出每一路的元素其实都在归并后的数组中，且这个数组可以保证其中的每个元素都是只包含2,3,5质因子。

正确算法1

C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        if(n <= 1) return n;
        vector<int> f(1,1);
        int i = 0, j = 0, k = 0;
        long long t = 0;
        while(--n)
        {
            t = min(f[i] * 2, min (f[j] * 3, f[k] * 5));
            if(t == f[i] * 2) i++;
            if(t == f[j] * 3) j++;
            if(t == f[k] * 5) k++;
            f.push_back(t);
        }
        return f.back();
    }
};

错误C++ 代码

class Solution {
public:
    int getUglyNumber(int n) {
        if(n <= 1) return n;
        int i = 1;
        int j = 1;
        int k = 1;
        long long res = 0;
        while(--n)
        {
            res = min(i * 2, min (j * 3, k * 5));
          //  cout << res << endl;
            if(res >= i * 2) i++;
            if(res >= j * 3) j++;
            if(res >= k * 5) k++;
            //cout << res << endl;
        }
        return res;
    }
};