牛客3735题解：动态规划与多指针求解第n个丑数的O(n)算法

一、题目解读

牛客3735题要求求解第n个丑数，即只包含质因子2、3、5的正整数序列中的第n项。

二、解题思路

核心思想为：

1. 动态规划：维护已生成的丑数数组，利用已知丑数推导后续丑数；

2. 多指针机制：通过三个指针分别指向当前可乘2/3/5的最小丑数位置，确保生成的丑数不重复且有序；

3. 最小选择：每次选择三个乘积（当前丑数×2、×3、×5）的最小值作为下一个丑数，并更新对应指针。

三、解题步骤

1. 边界处理：若n≤0直接返回0，初始化数组uglyNumbers长度为n，首项为1；

2. 初始化指针：p2、p3、p5均指向0，代表从第一个丑数开始乘2/3/5；

3. 循环生成丑数：

    计算三个指针对应的乘积next2/3/5；

    取三者最小值更新uglyNumbers[i]；

    若某乘积被选中，则对应指针后移（如uglyNumbers[i] == next2则p2++）；

4. 返回结果：数组末尾元素uglyNumbers[index-1]即为第n个丑数。

四、代码与注释

class Solution {
public:
    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个丑数
    }
};

五、总结

本解法通过动态规划结合多指针，将问题转化为有序序列的生成，时间复杂度O(n)，空间复杂度O(n)。关键在于利用丑数的数学性质（仅由2/3/5相乘得到），通过指针移动避免重复计算。适用于需要高效求解特定序列元素的场景，展现了算法设计中数学推导与优化技巧的结合。