当前位置：首页 > news >正文

丑数II C++三指针解法(力扣264)

news 2026/5/12 1:05:32

问题解构：LeetCode 264题“丑数II”要求找出第n个丑数。丑数定义为只包含质因数2、3、5的正整数（1通常被视为第一个丑数）。核心挑战在于高效生成有序的丑数序列，避免对每个数进行质因数分解判断（效率极低）。

方案推演：高效解法主要基于动态规划与三指针技术。思路是每个丑数都可以由之前的某个丑数乘以2、3或5得到。使用三个指针p2、p3、p5分别记录下一个可能乘以2、3、5的丑数位置，每次取生成值的最小值作为新丑数，并更新对应指针。

以下是完整的C++代码实现，包含详细注释。

#include <vector> #include <algorithm> using namespace std; class Solution { public: int nthUglyNumber(int n) { // 使用动态规划数组dp存储已生成的丑数 vector<int> dp(n); dp[0] = 1; // 第一个丑数是1 // 初始化三个指针，分别指向下一个将要乘以2、3、5的丑数位置 int p2 = 0, p3 = 0, p5 = 0; for (int i = 1; i < n; ++i) { // 生成下一个丑数的三个候选值 int num2 = dp[p2] * 2; int num3 = dp[p3] * 3; int num5 = dp[p5] * 5; // 下一个丑数是三个候选值中的最小值 int nextUgly = min({num2, num3, num5}); dp[i] = nextUgly; // 关键步骤：更新指针。如果候选值被选中，其对应的指针后移一位。 // 注意：使用if而非else if，因为可能存在多个候选值相等的情况（例如6=2*3），需要同时移动指针以避免重复。 if (nextUgly == num2) { p2++; } if (nextUgly == num3) { p3++; } if (nextUgly == num5) { p5++; } } // 返回第n个丑数 return dp[n - 1]; } };

算法核心逻辑与示例：

该算法通过维护三个指针p2、p3、p5和一个丑数序列dp，确保每次都能以O(1)的时间找到下一个丑数。其工作原理如下表所示：

步骤 (i)	dp[i] (丑数)	p2 (乘2基准)	p3 (乘3基准)	p5 (乘5基准)	候选值 (num2, num3, num5)	选中值	指针更新
初始	dp[0]=1	0 (dp[0]=1)	0 (dp[0]=1)	0 (dp[0]=1)	(2, 3, 5)	2	p2++
i=1	2	1 (dp[1]=2)	0 (dp[0]=1)	0 (dp[0]=1)	(4, 3, 5)	3	p3++
i=2	3	1 (dp[1]=2)	1 (dp[1]=2)	0 (dp[0]=1)	(4, 6, 5)	4	p2++
i=3	4	2 (dp[2]=3)	1 (dp[1]=2)	0 (dp[0]=1)	(6, 6, 5)	5	p5++
i=4	5	2 (dp[2]=3)	1 (dp[1]=2)	1 (dp[1]=2)	(6, 6, 10)	6	p2++, p3++

以上模拟展示了生成前6个丑数（1, 2, 3, 4, 5, 6）的过程。特别需要注意的是步骤i=4，候选值num2和num3都等于6，此时p2和p3需要同时递增，以防止后续序列中出现重复的丑数（如另一个6）。

复杂度分析：

时间复杂度：O(n)。只需进行单层循环生成n个丑数，每次循环内的操作是常数时间。
空间复杂度：O(n)。需要长度为n的数组dp来存储丑数序列。

性能优化提示：
在实际提交中，可以利用C++类的静态变量进行缓存优化。即，将丑数数组dp声明为静态变量，这样在多次调用nthUglyNumber函数时，可以复用之前计算好的丑数序列，避免重复计算，尤其适合在线判题系统的多组测试用例场景。

// 优化版本：使用静态变量缓存丑数序列 class SolutionOptimized { public: int nthUglyNumber(int n) { static vector<int> dp; static int p2 = 0, p3 = 0, p5 = 0; if (dp.empty()) { dp.push_back(1); } while (dp.size() < n) { int nextUgly = min({dp[p2] * 2, dp[p3] * 3, dp[p5] * 5}); dp.push_back(nextUgly); if (nextUgly == dp[p2] * 2) p2++; if (nextUgly == dp[p3] * 3) p3++; if (nextUgly == dp[p5] * 5) p5++; } return dp[n - 1]; } };

此优化版本在首次调用或需要扩展序列时进行计算，之后调用直接返回缓存结果，显著提升效率。