牛客3735题丑数：从暴力枚举到动态规划优化

丑数是指只包含质因子2、3和5的正整数。特别地，1也被视为第一个丑数。例如，前10个丑数序列为：1, 2, 3, 4, 5, 6, 8, 9, 10, 12。

一、问题分析

我们需要找到按从小到大排列的第n个丑数。直观的解法可能是：

1. 从1开始逐个检查每个数是否为丑数

2. 直到找到第n个丑数

但这种方法效率极低，时间复杂度为O(nlogn)，对于n=2000来说性能不够理想。

二、动态规划解法

更高效的解法是使用动态规划，时间复杂度O(n)，空间复杂度O(n)。核心思想是：

1. 丑数生成规律：每个丑数都是由更小的丑数乘以2、3或5得到的

2. 指针跟踪：维护三个指针，分别记录下一个丑数可能由哪个数乘以2、3或5产生

3. 最小值选择：每次选择三个可能值中的最小值作为下一个丑数

三、算法步骤详解

1. 初始化：

• 创建数组存储丑数序列，第一个元素为1

• 初始化三个指针p2、p3、p5都指向第一个丑数

2. 生成过程：

• 计算ugly[p2]*2、ugly[p3]*3、ugly[p5]*5

• 选择三者中的最小值作为下一个丑数

• 更新对应指针（如果最小值等于某个计算值，则该指针前移）

3. 终止条件：

• 当生成n个丑数后停止

四、完整代码

class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param index int整型
     * @return int整型
     */
    int GetUglyNumber_Solution(int index) {
        if (index <= 0) return 0; // 处理边界情况

        vector<int> uglyNumbers(index); // 存储丑数的数组
        uglyNumbers[0] = 1; // 第一个丑数是1

        // 初始化三个指针，分别对应2、3、5的乘数位置
        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < index; ++i) {
            // 计算三个指针指向的丑数分别乘以2、3、5的最小值
            int next2 = uglyNumbers[p2] * 2;
            int next3 = uglyNumbers[p3] * 3;
            int next5 = uglyNumbers[p5] * 5;

            // 下一个丑数是这三个值中的最小值
            uglyNumbers[i] = min(next2, min(next3, next5));

            // 更新指针：如果某个指针产生的值被选中，则该指针前移
            if (uglyNumbers[i] == next2) p2++;
            if (uglyNumbers[i] == next3) p3++;
            if (uglyNumbers[i] == next5) p5++;
        }

        return uglyNumbers[index - 1]; // 返回第n个丑数
    }
};

五、为什么这种方法有效？

这种方法确保了：

• 每个丑数都被生成且只生成一次

• 生成的顺序是从小到大排列的

• 避免了不必要的计算，只计算需要的乘积

六、代码实现要点

1. 边界处理：n<=0时返回0

2. 指针更新：注意可能有多个指针需要同时更新（当多个乘积等于最小值时）

3. 空间优化：只需要存储丑数序列，无需额外空间

七、常见错误与调试

1. 指针更新不全：当多个乘积等于最小值时，需要更新所有对应的指针

2. 数组越界：确保数组大小足够存储n个元素

3. 整数溢出：当n较大时，丑数值可能超出int范围（本题n≤2000不会溢出）