题目描述

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

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

求第 n 个丑数的值。

数据范围

1≤n≤1000

样例

输入：5
输出：5
• 1
• 2
• 3

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

方法一：动态规划 O(n)

我们可以利用多路归并思想，动态的更新值。

假设一个序列 S ，其中包含了所有丑数即只包含质因子 2 、3 和 5 的数。那么如果那么现在有三个序列，这三个序列分别只包含质因子 2 、3 和 5 的数，则这三个序列并集就等于序列 S 。所以我们可以用三个指针分别指向这三个序列的第一个元素，每次都只取这三个指针指向的最小值加入答案数组，并将该指针往后移，直到得到第 n 个丑数。

我们可以对上述思路进行优化，只用一个数组来存储得到的丑数，三个指针指向开头，每得到一个最小值就加入该数组末尾，然后将指针后移一位再进行比较，这样可以保证所有数都不会被忽略。我们拿题目的样例 n = 5 举例，来看看具体的思路是如何：

第一步： 先将 1 加入数组中，因为这是一个特殊的样例，需要进行初始化，且将 i 、j 和 k 都指向 q[0] 。其中 i 用于指向只包含质因数 2 的序列，j 则指向只包含质因数 3 的序列，k 则指向只包含质因数 5 的序列。

第二步： 从三个指针指向的元素中取最小值，即 t = m i n ( 1 ∗ 2 , 1 ∗ 3 , 1 ∗ 5 ) = m i n ( 2 , 3 , 5 ) = 2 ，故将 i 往后移一位。

第三步： 从三个指针指向的元素中取最小值，即 t = m i n ( 2 ∗ 2 , 1 ∗ 3 , 1 ∗ 5 ) = m i n ( 4 , 3 , 5 ) = 3 t = min(2 * 2 , 1 * 3 , 1 * 5)=min(4,3,5)=3t=min(2∗2,1∗3,1∗5)=min(4,3,5)=3 ，故将 j 往后移一位。

第四步： 从三个指针指向的元素中取最小值，即 t = m i n ( 2 ∗ 2 , 2 ∗ 3 , 1 ∗ 5 ) = m i n ( 4 , 6 , 5 ) = 4 故将 i 往后移一位。

第五步： 从三个指针指向的元素中取最小值，即 t = m i n ( 3 ∗ 2 , 1 ∗ 3 , 1 ∗ 5 ) = m i n ( 6 , 6 , 5 ) = 5 故将 k 往后移一位。

第六步: 此时容器中已经有 5 个元素，直接返回最后一个元素 5 即可。

class Solution {
public:
    int getUglyNumber(int n) {
        vector<int> q(1, 1); //初始化第一个丑数1
        int i = 0, j = 0, k = 0;
        while (--n)
        {
            int t = min(q[i] * 2, min(q[j] * 3, q[k] * 5));
            q.push_back(t);
            if (q[i] * 2 == t) i++;
            if (q[j] * 3 == t) j++;
            if (q[k] * 5 == t) k++;
        }
        return q.back();
    }
};

欢迎大家在评论区交流~