LeetCode 剑指 Offer 49. 丑数

约 10 分钟
文章信息 10 个分类 5 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节跳动 腾讯 华为 剑指 Offer 剑指 Offer（第 2 版）
标签
哈希表 动态规划 数学 堆（优先队列） 数学经典题
目录

题目描述

✅ 剑指 Offer 49. 丑数

image-20241107211647748

题意分析

丑数指的是质因数只包含 $2$、$3$、$5$ 的正整数，题目额外规定 $1$ 也是丑数，并且它是第一个。要求返回从小到大排列的第 n 个丑数。

「只包含」是排他式的表述，不是并列式的。一个数只要不含 $2$、$3$、$5$ 之外的质因数就算，并不要求这三个因子都出现，所以 $2$、$3$、$4$、$8$、$9$ 全都是丑数。把它误读成「必须同时含有」，序列从第一个元素起就全错。

答案必须是有序序列中的第 n 项，这意味着解法不仅要能产出丑数，还要保证产出的顺序严格递增且不重复。

n 的上限是 $1690$，这个看似奇怪的数字其实是一条约束信号：第 $1690$ 个丑数是 $2123366400$，已经逼近 32 位有符号整数的上界，再往后就装不下了。它同时说明丑数在整数轴上极其稀疏——要数到第 $1690$ 个，得跨过二十一亿个整数。

边界只有一处：n 等于 $1$ 时答案是 $1$，写法上应当让它由初始化自然给出，而不是额外判一次。

解法：三指针动态规划

核心思路

最直接的想法是从 $1$ 开始逐个整数检验：反复除以 $2$、$3$、$5$，如果最后剩下 $1$ 就是丑数，数够 n 个为止。它的瓶颈很致命——丑数越往后越稀疏，要拿到第 $1690$ 个就得检验二十一亿个候选，绝大部分工作都花在了确认某个数「不是」丑数上。

换个方向：不去筛选，而去生成。除 $1$ 之外，任何丑数的质因数分解里至少有一个 $2$、$3$ 或 $5$，把其中一个除掉，剩下的仍然是丑数且更小。反过来说，每个丑数都可以由某个更小的丑数乘上 $2$、$3$ 或 $5$ 得到。于是整个序列可以从 $1$ 出发自我生长，完全不必碰非丑数。

状态定义为：dp[i] 表示第 $i + 1$ 个丑数（下标从 $0$ 起），dp[0] = 1。

剩下的问题是怎么保证生成顺序。把生成看成三条流水线：一条负责把已有丑数乘 $2$，一条乘 $3$，一条乘 $5$。每条流水线内部是递增的，因为它的输入 dp 本身递增。于是用三个指针 p2、p3、p5 分别标记各条流水线下一个该取用的输入位置，维持的不变量是：dp[p2] * 2 是所有「乘 $2$ 通道」尚未被写入序列的乘积中最小的一个，p3、p5 同理。

有了这条不变量，下一个丑数就必然是这三个候选中的最小值——因为任何还没出现的丑数都属于某条通道，而每条通道能提供的最小未用值就是这三个。取完最小值写入 dp[i] 之后，凡是等于该最小值的候选，其对应指针都要前进一格，这样不变量才继续成立。

「凡是等于就都前进」这一句是去重的全部机制。像 $6$ 这样既能由 $3 \times 2$ 也能由 $2 \times 3$ 得到的数，会同时出现在两条通道的候选里，只推进一个指针的话，另一条通道下一轮还会再吐出一次 $6$，序列里就会出现重复项，后面所有编号全部错位。

解题步骤

  • 开一个长度为 n 的数组 dp，令 dp[0] = 1。这个 $1$ 既是题目规定的第一个丑数，也是所有后续丑数的生成源头，缺了它整条流水线没有输入。
  • 把 p2、p3、p5 全部初始化为 $0$，都指向 dp[0]。三条通道都必须从最小的丑数开始取用，否则最开始的几个乘积就会被跳过。
  • 从 i = 1 循环到 n - 1，每轮先算出三个候选 dp[p2] * 2、dp[p3] * 3、dp[p5] * 5。必须每轮重新计算，因为指针可能刚在上一轮移动过。
  • 取三个候选的最小值写入 dp[i]。三个都要参与比较，漏掉任何一个都会让对应质因子的丑数永远进不了序列。
  • 依次用三个独立的 if 判断哪些候选等于本轮最小值，命中的指针各自加一。这里必须是三个平行的 if 而不是 if / else if 链，否则重复值只会推进一个指针。
  • 循环结束返回 dp[n - 1]。n 等于 $1$ 时循环体一次都不执行，直接返回初始化好的 dp[0]，边界自动闭合。

以 n = 10 走一遍：初始 dp[0] = 1，三个指针都为 $0$。

i = 1：候选为 $1 \times 2 = 2$、$1 \times 3 = 3$、$1 \times 5 = 5$，最小是 $2$，写入 dp[1] = 2，只有乘 $2$ 通道命中，p2 变为 $1$。

i = 2：候选为 $dp[1] \times 2 = 4$、$dp[0] \times 3 = 3$、$dp[0] \times 5 = 5$，最小是 $3$，写入 dp[2] = 3，p3 变为 $1$。

i = 3：候选为 $4$、$dp[1] \times 3 = 6$、$5$，最小是 $4$，写入 dp[3] = 4，p2 变为 $2$。

i = 4：候选为 $dp[2] \times 2 = 6$、$6$、$5$，最小是 $5$，写入 dp[4] = 5，p5 变为 $1$。

i = 5：候选为 $6$、$6$、$dp[1] \times 5 = 10$，最小是 $6$。写入 dp[5] = 6，此时前两个候选都等于最小值，p2 变为 $3$、p3 变为 $2$，两条通道同时跳过这个重复的 $6$。

i = 6：候选为 $dp[3] \times 2 = 8$、$dp[2] \times 3 = 9$、$10$，最小是 $8$，写入 dp[6] = 8，p2 变为 $4$。

i = 7：候选为 $dp[4] \times 2 = 10$、$9$、$10$，最小是 $9$，写入 dp[7] = 9，p3 变为 $3$。

i = 8：候选为 $10$、$dp[3] \times 3 = 12$、$10$，最小是 $10$，写入 dp[8] = 10，乘 $2$ 和乘 $5$ 两条通道都命中，p2 变为 $5$、p5 变为 $2$。

i = 9：候选为 $dp[5] \times 2 = 12$、$12$、$dp[2] \times 5 = 15$，最小是 $12$，写入 dp[9] = 12，p2 变为 $6$、p3 变为 $4$。

循环结束，返回 dp[9] = 12。核对生成的序列 $1, 2, 3, 4, 5, 6, 8, 9, 10, 12$，严格递增且无重复，第 $10$ 项正是 $12$。

代码实现

class Solution {
    // 三个指针分别指向下一个可以乘 2、乘 3、乘 5 的已有丑数，每轮取三个候选中的最小值。
    public int nthUglyNumber(int n) {
        int[] dp = new int[n];
        dp[0] = 1;

        int p2 = 0;
        int p3 = 0;
        int p5 = 0;

        for (int i = 1; i < n; i++) {
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;
            int next = Math.min(next2, Math.min(next3, next5));
            dp[i] = next;

            if (next == next2) {
                p2++;
            }
            if (next == next3) {
                p3++;
            }
            if (next == next5) {
                p5++;
            }
        }

        return dp[n - 1];
    }
}

func nthUglyNumber(n int) int {
    // 三个指针分别指向下一个可以乘 2、乘 3、乘 5 的已有丑数，每轮取三个候选中的最小值。
    dp := make([]int, n)
    dp[0] = 1
    p2, p3, p5 := 0, 0, 0

    for i := 1; i < n; i++ {
        next2 := dp[p2] * 2
        next3 := dp[p3] * 3
        next5 := dp[p5] * 5
        next := next2
        if next3 < next {
            next = next3
        }
        if next5 < next {
            next = next5
        }

        dp[i] = next
        if next == next2 {
            p2++
        }
        if next == next3 {
            p3++
        }
        if next == next5 {
            p5++
        }
    }

    return dp[n-1]
}

复杂度分析

  • 时间复杂度：$O(n)$。循环恰好执行 $n - 1$ 轮，每轮只做三次乘法、两次比较取最小、三次相等判断和至多三次自增，全是常数操作。与逐个整数检验的做法相比，它跳过了所有非丑数，代价从「答案的大小」降到了「答案的编号」。
  • 空间复杂度：$O(n)$，dp 数组保存前 n 个丑数。这份存储无法压缩：三个指针会指向相距很远的历史位置，例如推进最慢的乘 $5$ 通道随时可能回取很早的丑数，只保留最近几项会直接取不到值。

关键点总结

  • 当目标元素在整数轴上稀疏分布时，把「筛选」换成「生成」往往是数量级的改进。判断的代价与数值大小挂钩，生成的代价只与个数挂钩。
  • 多路有序流水线合并时，用「每条通道一个指针」代替优先队列，是把 $O(n \log n)$ 压到 $O(n)$ 的常见手法。前提是通道数量固定且每条通道自身有序。
  • 指针类不变量要能一句话说清：p2 指向「乘 $2$ 之后尚未被写入序列的最小丑数」。定义清楚之后，「取最小」和「推进指针」这两个动作的正确性都是它的直接推论。
  • 去重靠的是「所有命中最小值的指针都前进」，而不是事后检查是否与上一项相同。这个写法把去重内建进了不变量的维护里，比补丁式的判重更可靠。
  • 面试视角：面试官常先让你写堆加哈希表的版本，再问能不能去掉堆。要能指出候选只有三条来源、且每条来源自身递增，因此维护三个下标就够了，这一步是本题的核心加分项。
  • 面试视角：高频追问是「质因子换成任意集合怎么办」。答案是把三个指针推广成长度为 k 的指针数组，每轮扫一遍求最小并推进所有命中者，时间变成 $O(nk)$，这正是超级丑数那道题。

易错点总结

  • 错误写法：更新指针时用 if / else if 链，只推进第一个命中的指针 → 重复值会被二次产出。以 n = 10 为例，i = 5 写入 $6$ 后只有 p2 前进，i = 6 时乘 $3$ 通道又给出一个 $6$，序列变成 $1, 2, 3, 4, 5, 6, 6, 8, 9, 10$，返回 $10$ 而不是 $12$。
  • 错误写法：把「只包含质因数 $2$、$3$、$5$」理解成「必须同时含有这三个因子」→ $1$、$2$、$3$、$4$ 全被排除，第一个丑数就变成了 $30$，整条序列彻底错位。
  • 错误写法：dp[0] 初始化为 $0$ → 三个候选恒为 $0$，整个数组被填成零，返回 $0$。这个错误在 n 较小时也会立刻暴露，但常被误当成数组未初始化的问题去查。
  • 错误写法：三个指针初始化为 $1$ → 第一轮就去读还没赋值的 dp[1]，候选全为 $0$，dp[1] 被写成 $0$，序列从第二项起崩溃。
  • 错误写法：候选写成 dp[i - 1] * 2、dp[i - 1] * 3、dp[i - 1] * 5，只从上一个丑数生成 → 每轮最小值恒为 dp[i - 1] * 2，序列退化成 $1, 2, 4, 8, 16, \dots$，$3$、$5$、$6$ 全部丢失。
  • 错误写法：取最小值时漏掉一个候选，比如只比较乘 $2$ 和乘 $3$ 两路 → 乘 $5$ 通道永远没有机会胜出。以 n = 10 为例，i = 4 时会写入 $6$ 而不是 $5$，序列里再也不会出现 $5$、$10$、$15$。
  • 错误写法：为省内存只保留最近几个丑数而不是完整数组 → 乘 $5$ 通道推进得最慢，p5 会长时间停在很靠前的位置，一旦那一项已被丢弃就取不到值，必须完整保留前 n 项。
  • 错误写法：改用小顶堆生成却不做去重 → $6$ 会分别由 $2 \times 3$ 和 $3 \times 2$ 两次入堆，弹出两次，从此每个编号都比真实位置偏后，必须配一张哈希表记录已入堆的值。
  • 错误写法：为 n = 1 单独加特判并返回 $0$ 或 $2$ → 循环体本就不执行，直接返回 dp[0] = 1 才是正确的；多写的特判反而制造了一个只在最小输入上出现的错误。

相似题目

题目 难度 考察点
264. 丑数 II 中等 与本题同题，官方题解同时给出堆加去重与三指针，适合对照两种复杂度
263. 丑数 简单 只判断单个数是否为丑数，考察反复除尽的写法与非正数的边界
313. 超级丑数 中等 质因子集合变成任意长度，三个指针推广为指针数组，时间变成 $O(nk)$
1201. 丑数 III 中等 定义改为能被 a、b、c 之一整除，靠容斥计数加二分求第 n 项，不再生成
面试题 17.09. 第 k 个数 中等 质因子换成 $3$、$5$、$7$，可用来检验指针逻辑是否写死了具体倍数
378. 有序矩阵中第 K 小的元素 中等 同为多路有序序列求第 k 小，但路数随规模变化，需要堆或值域二分