LeetCode 剑指 Offer 49. 丑数

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

题目描述

✅ 剑指 Offer 49. 丑数

image-20261001230752574

image-20260928201405308

题意分析

丑数是质因数只可能包含 2、3、5 的正整数，并规定 1 是第一个丑数。按从小到大、不重复的顺序排列这些数，求第 n 个。

不要求三个质因数都出现，只要没有其他质因数即可。题图求的是第 1500 个，下面把序号写成参数 n，用同一种生成方法求指定位置。

解法：三指针动态规划

核心思路

[!blue]

每个大于一的丑数都至少含有一个因子 2、3 或 5。去掉其中一个因子后，剩下的仍是更小的丑数；反过来，已有丑数乘这三个数之一，也一定还是丑数。因此所有后续答案都能从已生成的序列中得到。

把丑数序列分别乘以 2、3、5，就得到三条各自递增的候选序列。用 p2、p3、p5 分别指向每条序列中尚未输出的最小候选，对应值为 dp[p2] * 2、dp[p3] * 3、dp[p5] * 5。

下一项必须是三路候选中的最小值：它既是合法丑数，也不会跳过任何更小的未输出丑数。写入后，凡是候选等于这一项的指针都要前进。每条候选序列内部严格递增，前进一步后就越过了刚输出的值；不同生成方式得到的同一个数也因此只输出一次。

没命中的指针保持不动，因为它仍代表该路最小的未使用候选。每轮之后，三路指针的含义继续成立，所以可以一直合并到第 n 项。起点必须为 dp[0] = 1，最后返回零基下标 n - 1。

解题步骤

  1. 创建长度为 n 的结果序列，令 dp[0] = 1，三个指针都从下标零开始。
  2. 计算三路乘积，取最小值写入当前答案位置。
  3. 使用三个独立判断，推进所有候选等于该最小值的指针。
  4. 生成到第 n 项后返回 dp[n - 1]；n == 1 时直接由初始化得到答案。

代码实现

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)$，每轮只计算三个候选并进行常数次比较。
  • 空间复杂度：$O(n)$，保存三个指针仍可能访问的历史丑数。

关键点总结

[!green]

  • 去掉一个允许的质因数后仍是丑数，保证三路生成不会遗漏。
  • 指针指向每一路最小的未输出候选，而不是统一指向上一项。
  • 所有命中最小值的指针都推进，去掉跨序列的重复值。

易错点总结

[!yellow]

  • 把三个判断写成 else if，只会推进一路，另一条路下一轮还会重复输出相同值。
  • 只把上一项乘二、三、五，会跳过较早历史项生成的更小候选。
  • 初始值不能为零，否则全部乘积都停留在零；一是生成整个序列的起点。
  • 第一个丑数编号为一，而数组下标从零开始，返回位置应为 n - 1。
  • 不能要求一个丑数同时包含二、三、五，允许其中某些因子的指数为零。

相似题目

题目 难度 关联与区别
313. 超级丑数 中等 把固定因子2、3、5推广为给定质数集合，仍需合并候选并跳过重复生成值。
面试题 17.09. 第 k 个数 中等 三指针方法相同，原题允许的因子为3、5、7，候选乘法需按范围使用宽整数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/77387514
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！