LeetCode 264. 丑数 II

约 5 分钟
文章信息 16 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 20-50 腾讯 字节 阿里 华为 微软 美团 拼多多 小米 百度 快手 滴滴
标签
哈希表 动态规划 数学 堆（优先队列）

题目描述

✅ 264. 丑数 II

image-20260928201405308

题意分析

将所有只含质因子 2、3、5 的正整数从小到大排列，返回第 n 个。因子不需要三种都出现，1 也被定义为丑数；相同数值无论能用多少种乘法生成，在序列里都只能出现一次。

n 表示第几个丑数，不是数值上限，也不是统计不超过 n 的丑数数量。题目范围为 1 <= n <= 1690。

解法：三指针动态生成

核心思路

[!blue]

除了起点 1，任何丑数都能除去一个因子 2、3 或 5，得到更小的丑数；反过来，丑数乘这三个因子也仍然是丑数。因此可以从已经生成的结果构造后继，无需逐个检查普通整数。

令 dp 保存严格递增的丑数序列。把其中每一项分别乘 2、3、5，就得到三条有序候选序列。p2、p3、p5 分别指向各自序列中尚未写入答案的最小候选，当前候选是 dp[p2] * 2、dp[p3] * 3、dp[p5] * 5。

下一项就是三个候选中的最小值：任何尚未生成的丑数都来自某条序列，不可能小于这条序列当前最小的未处理项；而这三个候选本身又都是合法丑数。取最小值便同时保证有序性和不漏数。

同一个值可能来自多条序列。写入一次后，所有产生该值的指针都必须前进，否则下一轮还会看到已写入的值，导致重复计数。因此三个推进条件必须是独立的 if，并且比较的是本轮事先保存的三个候选。

从 dp[0] = 1、三个指针均为零开始，重复生成到下标 n - 1 即可。每个指针的推进速度不同，必须各自维护，不能合并成一个位置。

解题步骤

  1. 创建长度为 n 的 dp，令 dp[0] = 1，并将 p2、p3、p5 初始化为零。
  2. 从 i = 1 到 n - 1，先计算并保存三条序列的当前候选。
  3. 取三个候选的最小值写入 dp[i]。
  4. 分别检查每个候选是否等于 dp[i]，相等就推进对应指针；可能同时推进多个。
  5. 返回 dp[n - 1]。当 n = 1 时不进入循环，直接得到起点。

代码实现

class Solution {
    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 {
    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 := min(next2, min(next3, 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)。三个指针需要访问此前生成的丑数，因此保存长度为 n 的序列。

关键点总结

[!green]

  • 丑数集合稀疏，应从已有丑数构造后继，而不是逐个检查普通整数。
  • 本题本质是合并三条有序生成链，三个指针各自记录消费进度。
  • 候选相等时必须推进所有来源，才能保证结果严格递增。
  • dp[0] = 1 是生成序列的起点；第 n 个数对应下标 n - 1。
  • 本题约束下，生成值和本轮候选均可用 int 表示。

易错点总结

[!yellow]

  • 用 if / else if 推进指针，会只消耗同值的一个来源，下一轮再次写入该值。
  • 忘记把 1 作为起点，会使整个序列的生成和序号错位。
  • 第 n 个丑数位于 dp[n - 1]，访问 dp[n] 会越界。
  • 应先保存本轮候选与最小值，再统一推进指针；推进后重算会混入下一轮候选。
  • 三条序列的消费速度不同，共用一个指针会跳过尚未选中的较小候选。

相似题目

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