leetcode 264. 丑数 II

题目：

https://leetcode.cn/problems/ugly-number-ii/description/?envType=study-plan-v2&envId=selected-coding-interview

问题描述

LeetCode 264题要求找到第n个丑数。丑数是指只包含质因数2、3、5的正整数，且习惯上认为第一个丑数是1。例如：

• 前10个丑数是：1, 2, 3, 4, 5, 6, 8, 9, 10, 12
• 输入：n = 10，输出：12

解题思路

要生成第n个丑数，可以使用动态规划的方法：

1. 初始化：第一个丑数为1，即dp[1] = 1。
2. 三指针法：维护三个指针p2、p3、p5，分别记录当前乘以2、3、5后能得到的最小丑数的位置。
3. 状态转移：每个新丑数都是由之前的某个丑数乘以2、3或5得到的，选择三者中的最小值作为下一个丑数，并更新对应的指针。

代码实现

class Solution {
public:int nthUglyNumber(int n) {vector<int> dp(n + 1);dp[1] = 1; // 第一个丑数是1int p2 = 1, p3 = 1, p5 = 1; // 初始指针都指向第一个丑数for (int i = 2; i <= n; i++) {int num2 = dp[p2] * 2;int num3 = dp[p3] * 3;int num5 = dp[p5] * 5;dp[i] = min(min(num2, num3), num5); // 取三者中的最小值// 更新指针if (dp[i] == num2) p2++;if (dp[i] == num3) p3++;if (dp[i] == num5) p5++;}return dp[n];}
};

代码解释

1. 动态规划数组：dp[i]表示第i个丑数。
2. 三指针：
   • p2：指向前一个乘以2后可能成为下一个丑数的位置。
   • p3：指向前一个乘以3后可能成为下一个丑数的位置。
   • p5：指向前一个乘以5后可能成为下一个丑数的位置。
3. 状态转移：
   • 每次生成新丑数时，选择dp[p2]*2、dp[p3]*3、dp[p5]*5中的最小值。
   • 如果选中某个值，则将对应的指针向后移动一位，确保不会重复计算。

复杂度分析

• 时间复杂度：O(n)，只需遍历一次数组。
• 空间复杂度：O(n)，需要存储前n个丑数。

通过这种方法，可以高效地生成第n个丑数，避免了暴力枚举的低效性。