【优先队列, 动态规划, 多路归并】丑数 II

题目

264. 丑数 II

---

给你一个整数 n ，请你找出并返回第 n 个 丑数 。

丑数 就是只包含质因数 2、3 和/或 5 的正整数。

示例 1：

输入：n = 10
输出：12
解释：[1, 2, 3, 4, 5, 6, 8, 9, 10, 12] 是由前 10 个丑数组成的序列。

示例 2：

输入：n = 1
输出：1
解释：1 通常被视为丑数。

提示：

• 1 <= n <= 1690

解题

方法一：小根堆(优先队列) 哈希表

思路

关于丑数：【数学, 迭代, 递归】丑数

如果一个数 $num$ 是丑数，那么 $2 \cdot num$ 、$3 \cdot num$ 、$5 \cdot num$ 也都是丑数。

而我们已知最小的丑数是 $1$，那么我们就可以利用最小堆(minHeap)，首先把 $1$ 加入最小堆，每次取出堆顶元素(num)，再把 num*2、num*3、num*5 放入堆中。
但是这样做可能会导致堆中存在重复元素，所以我们可以在每次堆顶元素出堆的时候把下一个堆顶元素与当前的 num 对比，如果相同就出堆，不断循环知道堆为空或者堆顶元素不与 num 相同，这样就可以达到去重的目的。
如果在堆中元素不重复的情况下，第 $n$ 次从堆中取出的元素即为第 $n$ 个丑数。

代码

class Solution {
    static final int[] FACTORS = {2, 3, 5};

    public int nthUglyNumber(int n) {
        Queue<Long> minHeap = new PriorityQueue<>();
        long num = 1L;
        while (--n > 0) {
            for (int factor : FACTORS) minHeap.offer(num * factor);
            num = minHeap.poll();
            while (!minHeap.isEmpty() && num == minHeap.peek()) minHeap.poll();
        }
        return (int) num;
    }
}

当然，也可以在元素入堆之前利用哈希表(seen)进行去重。

typedef long long ll;

class Solution {
    const int FACTORS[3] = {2, 3, 5};

public:
    int nthUglyNumber(int n) {
        priority_queue<ll, vector<ll>, greater<ll>> min_heap;
        unordered_set<ll> seen;
        ll num;
        min_heap.push(1L);
        seen.insert(1L);
        while (n--) {
            num = min_heap.top(), min_heap.pop();
            for (const int& factor : FACTORS) {
                ll new_num = num * factor;
                if (seen.find(new_num) == seen.end()) {
                    min_heap.push(new_num);
                    seen.insert(new_num);
                }
            }
        }
        return num;
    }
};

方法二：动态规划 / 多路归并

思路

定义数组 dp，其中 dp[i] 表示第 i+1 个丑数，第 n 个丑数即为 dp[n - 1]。

由于最小的丑数是 1，因此 dp[0] = 1。

如何得到其余的丑数呢？定义三个指针 p2、p3、p5，表示下一个丑数是当前指针指向的丑数乘以对应的质因数。初始时，三个指针的值都是 0。

当 1 <= i < n 时，令 dp[i] = min(dp[p2] * 2, dp[p3] * 3, dp[p5] * 5)，然后分别比较 dp[i] 和 dp[p2] * 2 、dp[p3] * 3、dp[p4] * 4是否相等，如果相等则将对应的指针后移。

参考：https://leetcode.cn/problems/ugly-number-ii/solution/chou-shu-ii-by-leetcode-solution-uoqd/

---

也可以理解为多路归并（多指针）：

从方法一中不难发现，我们「往后产生的数值」都是基于「已有数值」而来（使用「已有数值」乘上 $2$、$3$、$5$）。

因此，如果我们最终的数值序列为 $a_1,a_2,a_3,...,a_n$ 的话，序列中的每一个数都必然能够被以下三个序列（中的至少一个）覆盖：

• 由丑数 $\times 2$ 所得的有序序列：$1 \times 2、2 \times 2、3 \times 2、4 \times 2、5 \times 2、6 \times 2、8 \times 2 ...$
• 由丑数 $\times 3$ 所得的有序序列：$1 \times 3、2 \times 3、3 \times 3、4 \times 3、5 \times 3、6 \times 3、8 \times 3 ...$
• 由丑数 $\times 5$ 所得的有序序列：$1 \times 5、2 \times 5、3 \times 5、4 \times 5、5 \times 5、6 \times 5、8 \times 5 ...$

举个例子：假设我们需要求得 $[1,2,3,4,5,6,8]$ 丑数序列 $arr$ 的最后一位，那么该序列可以看作以下三个有序序列归并而来：

• $1 \times 2, 2 \times 2, 3 \times 2, ..., 6 \times 2, 8 \times 2$ ，将 $2$ 提出，即 $arr \times 2$
• $1 \times 3, 2 \times 3, 3 \times 3, ..., 6 \times 3, 8 \times 3$ ，将 $3$ 提出，即 $arr \times 3$
• $1 \times 5, 2 \times 5, 3 \times 5, ..., 6 \times 5, 8 \times 5$ ，将 $5$ 提出，即 $arr \times 5$

因此我们可以使用三个指针来指向目标序列 $arr$ 的某个下标，使用 $arr[下标] \times 系数$（2、3、5） 代表当前使用到三个有序序列中的哪一位，同时使用 i 表示当前生成到 arr 哪一位数值。

参考：【多路归并】从朴素优先队列到多路归并

代码

typedef long long ll;

class Solution {
public:
    int nthUglyNumber(int n) {
        ll dp[n];
        dp[0] = 1L;
        for (int p2 = 0, p3 = 0, p5 = 0, i = 1; i < n; ++i) {
            ll n2 = dp[p2] * 2, n3 = dp[p3] * 3, n5 = dp[p5] * 5;
            ll mn = min(n2, min(n3, n5));
            dp[i] = mn;
            if (n2 == mn) ++p2;
            if (n3 == mn) ++p3;
            if (n5 == mn) ++p5;
        }
        return dp[n - 1];
    }
};