核心思想：三路合并

集合 $\{a_i\}$ 表示至少包含一个因子 2 的丑数集合
集合 $\{b_i\}$ 表示至少包含一个因子 3 的丑数集合
集合 $\{c_i\}$ 表示至少包含一个因子 5 的丑数集合

丑数集合显然是上面三个集合的并集

但是呢，上面三个集合是不好求的

我们发现 $\{a_i / 2\},\{b_i/3\},\{c_i / 5\}$ 都是丑数集合

借助 $\{a_i / 2\},\{b_i/3\},\{c_i / 5\}$ 去还原 $\{a_i \},\{b_i\},\{c_i \}$

当我们先把 1 加到答案集合后，每当我需要用 $a_i$ 这个值时，可以发现在一步步把丑数添加到答案集合的过程中 $a_i / 2$ 这个值一定已经被求出，所以乘 2 后就得到了 $a_i$，同理可知 $b_j$ 和 $c_k$ 这样就可以进行三路合并了。

class Solution {
public:
    // 丑数 = a ∪ b ∪ c
    // 2: a1, ..., an.. 至少包含一个 2 的丑数序列
    // 3: b1, ..., bn..
    // 5: c1, ..., cn..

    // ai不方便直接求，所以借助已经求出的丑数ai/2，让它乘2 就得到了丑数ai

    // 2: a1 / 2, ..., an / 2.. 丑数序列
    // 3: b1 / 3, ..., bn / 3.. 丑数序列
    // 5: c1 / 5, ..., cn / 2.. 丑数序列
    int nthUglyNumber(int n) {
        vector<int> p(1, 1);

        int i = 0, j = 0, k = 0;
        while (--n) {
            int t = min(p[i] * 2, min(p[j] * 3, p[k] * 5));
            if (t == p[i] * 2) i ++;
            if (t == p[j] * 3) j ++;
            if (t == p[k] * 5) k ++;
            p.push_bacsk(t);
        }
        return p.back();
    }
};