摘要：在算法学习中，“丑数”问题是一道经典的数学与编程结合的题目，它不仅考察对数学定义的理解，更考验优化解题思路的能力。本文将从丑数的定义出发，拆解问题本质，逐步推导高效解法，并对比不同实现方式，帮助读者彻底掌握这一问题。
在算法学习中，“丑数”问题是一道经典的数学与编程结合的题目，它不仅考察对数学定义的理解，更考验优化解题思路的能力。本文将从丑数的定义出发，拆解问题本质，逐步推导高效解法，并对比不同实现方式，帮助读者彻底掌握这一问题。
首先明确丑数的数学定义：只包含因子2、3和5的正整数称为丑数，且习惯上把1作为第一个丑数。
符合条件的例子：6（2×3）、8（2³）、10（2×5），这些数的所有质因子仅为2、3、5；不符合条件的例子：14（包含因子7）、21（包含因子7），因为它们存在2、3、5之外的质因子。通过简单枚举可发现，前6个丑数依次是1、2、3、4、5、6——这一规律是后续优化解法的重要基础。
题目要求“按从小到大的顺序找到第N个丑数”，若直接采用“暴力法”，即对每个数依次判断是否为丑数，会存在明显效率问题：对于较大的N（如N=1000），需要遍历大量非丑数（如7、11、13等），时间复杂度极高。
此时需转换思路：从丑数的生成规律入手。根据定义，除1以外的所有丑数，都是由更小的丑数乘以2、3或5得到的。例如：
4 = 2×2（2是第2个丑数）；6 = 2×3（2是第2个丑数，3是第3个丑数）；9 = 3×3（3是第3个丑数）。这一规律启示我们：可以通过“主动生成丑数”替代“被动判断丑数”，用一个数组存储已排序的丑数，后续的丑数由数组中前面的元素推导而来。
若直接将数组中所有元素分别乘以2、3、5，再筛选最小值，会导致重复计算（如6可由2×3或3×2生成），且效率低下。解决这一问题的关键是跟踪“有效乘数位置”：
对于因子2、3、5，分别存在一个“临界位置”（记为t2、t3、t5），满足：
位置t2之前的丑数乘以2，结果均小于当前数组中最大的丑数（无需考虑，避免重复）；位置t2及之后的丑数乘以2，结果大于当前最大丑数（是候选新丑数）。同理，t3对应因子3的临界位置，t5对应因子5的临界位置。每次生成新丑数后，更新这三个临界位置，确保后续生成的丑数始终有序。
基于上述思路，我们可以设计出时间复杂度O(N)、空间复杂度O(N)的解法，以下分别给出C++和Python的实现，并解析关键步骤。
#include #include // 用于min函数using namespace std;class Solution {public:int GetUglyNumber_Solution(int index) {// 前6个丑数是1-6，直接返回indexif (index ugly_nums(index);// 初始化前6个丑数for (int i = 0; i = ugly_nums[t2] * 2) {t2++;}// 同理更新t3while (ugly_nums[i] >= ugly_nums[t3] * 3) {t3++;}// 同理更新t5while (ugly_nums[i] >= ugly_nums[t5] * 5) {t5++;}}// 返回第index个丑数（数组索引从0开始）return ugly_nums[index - 1];}};Python语法更简洁，无需手动管理数组大小，直接用列表动态追加元素即可：
# -*- coding:utf-8 -*-class Solution:def GetUglyNumber_Solution(self, index):# 前6个丑数直接返回if index 初始化优化：因前6个丑数固定为1-6，当index 临界位置初始化：t2=3：对应丑数4（索引3），4×2=8（下一个由2生成的丑数）；t3=2：对应丑数3（索引2），3×3=9（下一个由3生成的丑数）；t5=1：对应丑数2（索引1），2×5=10（下一个由5生成的丑数）；循环更新：每次生成新丑数后，通过while循环移动临界位置，确保下一次生成的候选值始终大于当前最大丑数，避免重复和无序。以“求第7个丑数”为例，验证算法逻辑：
初始数组：[1,2,3,4,5,6]，t2=3、t3=2、t5=1；计算候选值：4×2=8、3×3=9、2×5=10，最小值为8，加入数组后变为[1,2,3,4,5,6,8]；更新临界位置：8 >= 4×2 → t2=4（对应丑数5，5×2=10）；8 8 第7个丑数为8，与预期一致。若进一步求第8个丑数，候选值为5×2=10、3×3=9、2×5=10，最小值为9，加入数组后更新t3=3，逻辑同样成立。
丑数问题的核心是“从生成规律出发，通过跟踪临界位置保证有序性”，相比暴力法，该解法将时间复杂度从O(N×K)（K为判断一个数是否为丑数的时间）优化至O(N)，空间复杂度为O(N)（用于存储已生成的丑数）。
这一思路不仅适用于丑数问题，还可推广到“由固定因子生成有序序列”的同类问题（如仅包含因子2和3的数），是算法学习中“找规律+优化”思维的典型应用。
来源：码农世界
