丑数序列是一个有序序列,每个丑数都是前面的丑数乘以 2、3 或 55得到的。我们可以使用一个动态规划的方法来解决这个问题,使用三个指针来跟踪乘以 2、3 和 5 的位置。
class Solution {
public:
int getUglyNumber(int n) {
if (n <= 0) return 0; // 对于非法输入,返回0
if (n == 1) return 1; // 第一个丑数是1
vector<int> uglyNumbers(n);
uglyNumbers[0] = 1; // 初始化第一个丑数
// 初始化三个指针
int index2 = 0, index3 = 0, index5 = 0;
// 计算第n个丑数
for (int i = 1; i < n; i++) {
// 计算下一个丑数,它是之前丑数乘以2、3或5的最小值
int nextUgly = min(min(uglyNumbers[index2] * 2, uglyNumbers[index3] * 3), uglyNumbers[index5] * 5);
uglyNumbers[i] = nextUgly;
// 移动指针
while (uglyNumbers[index2] * 2 <= nextUgly) index2++;
while (uglyNumbers[index3] * 3 <= nextUgly) index3++;
while (uglyNumbers[index5] * 5 <= nextUgly) index5++;
}
// 返回第n个丑数
return uglyNumbers[n - 1];
}
};
驼峰式命名法大大好评