用最小堆或动态规划解决数据的滚动添加维护

题目链接-来源：力扣（LeetCode）

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例:

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:  

1 是丑数。
n 不超过1690。

思路：

基本思路是，丑数 能且仅能通过已有的丑数继续乘上 2、3、5 质因子生成。于是我们只要在获得一个新的丑数时，将其分别乘上 2、3、5 质因子然后加入后续的集合当中，就能保证不漏过任何一个丑数。添加丑数时，从该集合当中取出 最小值即可。容易想到，用 最小堆实现这个集合可以获得平均每次操作的时间复杂度 O(logn)。
这个方法的瑕疵在于，我们每取出 1 个丑数时，就要新添加 3 个丑数，等于每次额外添加了 2 个数，所以当进行 n 次操作后，我们会浪费 2n 的存储空间。
我们考虑用动态规划来实现。首先明确这样一个前提：每个出现过的丑数，可以拿来乘以 2、3、5 生成 3 个新的丑数，也就是说，这个丑数最多会被使用 3 次，且按 *2、*3、*5 的顺序依次使用各 1 次。
那么我们考虑用一个数组存储丑数， dp[i] 表示当前第 i 个丑数。用 3 个指针 p2、p3、p5 分别从下标为 0 处开始遍历丑数，指针 p2 代表的含义是，「该指针遍历过的数字已经乘过 2 了，而当前指向的数字还没有」， p3 和 p5 同理。那么每次我们需要生成新的丑数 dp[i]，就在 p2、p3、p5 对应的丑数中，取一个乘以对应质因子之后结果最小的数，作为新的丑数更新 dp[i]。这样，我们不仅节约了存储空间，还实现了O(n)时间的比较、取数操作。
时间复杂度：O(n)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;
        int p2 = 0, p3 = 0, p5 =0;
        for (int i = 1; i < n; i++) {
            dp[i] = Integer.min(dp[p2] * 2, Integer.min(dp[p3] * 3, dp[p5] * 5));
            if (dp[i] == dp[p2] * 2) {
                p2++;
            }
            if (dp[i] == dp[p3] * 3) {
                p3++;
            }
            if (dp[i] == dp[p5] * 5) {
                p5++;
            }
        }
        return dp[n - 1];
    }
}