第N个丑数

题目描述

课堂上我们学习了优先队列的知识，我们得知优先队列容器和队列一样，只能从队尾插入元素，从队首删除元素。

在优先队列中最大的元素总是位于队首，所以出队时，并不是完全一样的遵循先进先出的原则来进行的，而是将队列中最大的元素出队。这点有点儿类似于给队列里元素先进行一个排序，再按照顺序出队。

今天老师有一个问题需要求助大家：丑数是指不能被2，3，5以外的其他素数整除的数，把丑数从小到大排列起来，结果 如下：1，2，3，4，5，6，8，9，10，12，15，… 求第n个丑数m。

输入描述

读入一个整数n(1<=n<=10000)。

输出描述

输出一行"The ugly number is m."。

用例输入 1

3

用例输出 1

The ugly number is 3.

我们从 “问题本质→思路推导→代码逐行拆解→执行过程模拟→关键问题答疑” 五个层面，把这道题彻底讲透，确保每个细节都清晰。

一、先把问题 “嚼碎”：什么是丑数？

丑数的定义有两个核心：

1. 整除规则：只能被 2、3、5 这三个质数整除（不能被其他质数如 7、11、13 等整除）；
2. 序列规则：第一个丑数固定是 1，之后按从小到大排列（如 1,2,3,4,5,6,8...）。

举几个例子帮你判断：

• 4 是丑数：4 = 2×2（只含 2，没有其他质数）；
• 6 是丑数：6 = 2×3（只含 2 和 3）；
• 7 不是丑数：只能被 7 整除（7 是其他质数）；
• 14 不是丑数：14 = 2×7（含了 7 这个额外质数）。

我们的目标是：输入一个整数 n（1≤n≤10000），找到这个序列里的第 n 个数。

二、思路怎么来？从 “笨办法” 到 “高效办法”

1. 先想 “笨办法”：逐个检查所有数

最直接的思路是：从 1 开始，每个数都检查是否是丑数，直到找到第 n 个。
但这个办法有个致命问题 ——效率太低。比如找第 10000 个丑数，中间会跳过大量非丑数（如 7、11、13...），浪费很多时间，肯定不符合要求。

2. 换个聪明思路：利用丑数的 “生成特性”

丑数有个关键数学特性：任何丑数 × 2 / ×3 / ×5 后，得到的还是丑数。
比如：

• 2 是丑数 → 2×2=4（丑数）、2×3=6（丑数）、2×5=10（丑数）；
• 3 是丑数 → 3×2=6（丑数）、3×3=9（丑数）、3×5=15（丑数）。

这意味着：所有丑数都能从更小的丑数 “生” 出来，不用再检查非丑数了！

3. 怎么保证 “从小到大” 生成？用最小堆

生成丑数时，我们需要每次都拿到 “当前最小的丑数”（才能按顺序排）—— 这正好是「最小堆（优先队列）」的强项：

• 最小堆的特性：堆顶永远是最小的元素，取堆顶只需 O (1) 时间；
• 生成新丑数后，扔进堆里，堆会自动调整，下次仍能快速取最小。

4. 怎么避免重复？用哈希集合

比如 6 可以由 2×3 生成，也可以由 3×2 生成 —— 如果不处理，堆里会有重复的 6，浪费时间。
这时候用「哈希集合（unordered_set）」记录已经处理过的丑数：

• 生成新丑数后，先查集合：如果没出现过，再加入堆和集合；
• 哈希集合的查找速度是 O (1)，效率很高。

三、代码逐行拆解：每个部分干什么？

先看完整代码，再逐行解析：

#include <iostream>       // 用于输入（cin）和输出（cout）
#include <queue>          // 提供优先队列（堆）的功能
#include <unordered_set>  // 提供哈希集合的功能using namespace std;       // 简化代码，不用每次写 std::（比如 std::cin 直接写 cin）int main() {// 1. 读取输入：用户要找第 n 个丑数int n;                  // 定义变量 n，存储用户输入的数字cin >> n;               // 从键盘读取 n（比如输入 3，就是找第 3 个丑数）// 2. 初始化核心数据结构：最小堆 + 哈希集合// 最小堆：存储待处理的丑数，每次取最小的// 模板参数说明：// - long long：堆里存的是长整型（防止丑数太大溢出）// - vector<long long>：堆的底层用 vector 容器实现// - greater<long long>：堆的比较规则，让堆成为“最小堆”（默认是最大堆）priority_queue<long long, vector<long long>, greater<long long>> minHeap;// 哈希集合：记录已经处理过的丑数，避免重复unordered_set<long long> seen;// 3. 启动：第一个丑数是 1，先放进堆和集合minHeap.push(1);    // 把 1 加入堆seen.insert(1);     // 把 1 加入集合，标记为“已处理”// 4. 定义变量：存储最终找到的第 n 个丑数long long ugly;     // 用 long long 是怕丑数太大，int 存不下// 5. 核心循环：循环 n 次，每次找一个丑数，第 n 次就是答案for (int i = 0; i < n; ++i) {  // i 从 0 到 n-1，共循环 n 次// 5.1 取当前最小的丑数（堆顶）ugly = minHeap.top();  // 把堆顶的最小数赋值给 uglyminHeap.pop();         // 把堆顶的数删掉（已经取出来用了）// 5.2 生成新丑数：当前丑数 ×2，处理重复后加入堆和集合long long next2 = ugly * 2;  // 生成新丑数：当前丑数×2// 查集合：如果 next2 没出现过（find 返回 end 表示没找到）if (seen.find(next2) == seen.end()) {seen.insert(next2);      // 标记 next2 为“已处理”minHeap.push(next2);     // 把 next2 加入堆，等待后续处理}// 5.3 生成新丑数：当前丑数 ×3，逻辑和 ×2 一样long long next3 = ugly * 3;if (seen.find(next3) == seen.end()) {seen.insert(next3);minHeap.push(next3);}// 5.4 生成新丑数：当前丑数 ×5，逻辑同上long long next5 = ugly * 5;if (seen.find(next5) == seen.end()) {seen.insert(next5);minHeap.push(next5);}}// 6. 输出结果：按题目要求的格式打印cout << "The ugly number is " << ugly << "." << endl;return 0;  // 程序正常结束
}

简洁版：

#include <iostream>
#include <queue>
#include <unordered_set>
using namespace std; 
int main()
{int n;cin >> n;priority_queue<long long, vector<long long>, greater<long long>> minHeap;unordered_set<long long> seen;minHeap.push(1);seen.insert(1);long long ugly;for (int i = 0; i < n; ++i) {ugly = minHeap.top();minHeap.pop();long long next2 = ugly * 2;if (seen.find(next2) == seen.end()) {seen.insert(next2);minHeap.push(next2);}long long next3 = ugly * 3;if (seen.find(next3) == seen.end()) {seen.insert(next3);minHeap.push(next3);}long long next5 = ugly * 5;if (seen.find(next5) == seen.end()) {seen.insert(next5);minHeap.push(next5);}}cout << "The ugly number is " << ugly << "." << endl;return 0;
}

四、用例子模拟执行：看代码怎么跑起来

以 “输入 n=3，找第 3 个丑数” 为例，一步步看堆和集合的变化：

初始状态

• 堆（minHeap）：[1]（堆顶是 1）
• 集合（seen）：{1}
• 变量 ugly：未赋值

第 1 次循环（i=0）：找第 1 个丑数

1. 取堆顶：ugly = 1，然后删除堆顶 → 堆变为空；
2. 生成新丑数：
   • 1×2=2：集合里没有 2 → 加入集合（{1,2}），加入堆 → 堆变为 [2]；
   • 1×3=3：集合里没有 3 → 加入集合（{1,2,3}），加入堆 → 堆变为 [2,3]；
   • 1×5=5：集合里没有 5 → 加入集合（{1,2,3,5}），加入堆 → 堆变为 [2,3,5]；
3. 此时 ugly=1（这是第 1 个丑数）。

第 2 次循环（i=1）：找第 2 个丑数

1. 取堆顶：ugly = 2，删除堆顶 → 堆变为 [3,5]；
2. 生成新丑数：
   • 2×2=4：集合里没有 4 → 加入集合（{1,2,3,4,5}），加入堆 → 堆变为 [3,5,4]（堆会自动调整为 [3,4,5]）；
   • 2×3=6：集合里没有 6 → 加入集合（{1,2,3,4,5,6}），加入堆 → 堆变为 [3,4,5,6]；
   • 2×5=10：集合里没有 10 → 加入集合（{1,2,3,4,5,6,10}），加入堆 → 堆变为 [3,4,5,6,10]；
3. 此时 ugly=2（这是第 2 个丑数）。

第 3 次循环（i=2）：找第 3 个丑数

1. 取堆顶：ugly = 3，删除堆顶 → 堆变为 [4,5,6,10]；
2. 生成新丑数：
   • 3×2=6：集合里已有 6 → 跳过；
   • 3×3=9：集合里没有 9 → 加入集合，加入堆 → 堆变为 [4,5,6,10,9]（调整为 [4,5,6,9,10]）；
   • 3×5=15：集合里没有 15 → 加入集合，加入堆 → 堆变为 [4,5,6,9,10,15]；
3. 此时 ugly=3（这是第 3 个丑数）。

循环结束，输出结果

打印：The ugly number is 3.（和用例一致）

五、关键问题答疑：为什么这么设计？

1. 为什么用 long long 而不是 int？
   丑数增长极快，比如第 1690 个丑数是 2147483648，而 int 的最大值是 2147483647（约 20 亿），用 int 会 “溢出”（数值变错），long long 能存更大的数（最大约 9 万亿），足够应对 n≤10000 的需求。

2. 堆的底层为什么用 vector？
   优先队列（priority_queue）是 “适配器”，需要基于一个底层容器实现（比如 vector、deque）。vector 是最常用的选择，因为它的随机访问效率高，方便堆调整（堆的本质是完全二叉树，用数组 /vector 存储最紧凑）。

3. 哈希集合为什么能去重？
   unordered_set 的特点是 “存储不重复的元素”，并且查找元素的速度是 O (1)（比数组的 O (n) 快很多）。每次生成新丑数时，先查集合：如果存在，说明之前已经处理过，直接跳过；如果不存在，再加入堆和集合，避免重复。

4. 循环 n 次就能得到第 n 个丑数？
   是的。因为每次循环都会 “取出当前最小的丑数”，第 1 次循环取第 1 小的丑数，第 2 次取第 2 小的，…… 第 n 次取的就是第 n 小的丑数，正好是我们要的答案。

总结

这道题的核心是 “利用丑数的生成特性 + 用最小堆保证顺序 + 用哈希集合去重”：

• 特性是 “丑数生丑数”，避免检查非丑数；
• 最小堆是 “按顺序取丑数” 的工具；
• 哈希集合是 “避免重复” 的工具。

代码的逻辑环环相扣，每个数据结构都在解决一个具体问题，理解了这三点，就能轻松掌握这道题。