49. 丑数
1. 描述
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
2. 例子
示例 1:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
3. 说明
- 1 是丑数。
- n 不超过1690。
4. 题解
时间复杂度: O(n)
空间复杂度: O(n)
我们知道在 O(logn) 时间复杂度内判断丑数的方式，但是如果要每个数字都判断是不是丑数，则会导致每次判断丑数过程中一些有用的中间量被浪费，因此我们使用动态规划算法来计算该题。
uglyNumber[i] 意味着第 i 个丑数
dp = uglyNumber
$ dp[i] = \begin{cases} 1, & \text{i == 1} \\
min(dp[末位2的倍数丑数下标]*2, min(dp[末位3的倍数丑数下标]*3, dp[末位5的倍数丑数下标]*5)) , & \text{i > 1} \\
\end{cases} $
class Solution
{
public:
int nthUglyNumber(int n)
{
vector<int> uglyNumber(n, 1);
int multipleIndex2 = 0, multipleIndex3 = 0, multipleIndex5 = 0;
for(int i = 1; i < n; i++)
{
int new2Multiple = uglyNumber[multipleIndex2] * 2;
int new3Multiple = uglyNumber[multipleIndex3] * 3;
int new5Multiple = uglyNumber[multipleIndex5] * 5;
uglyNumber[i] = min(new2Multiple, min(new3Multiple, new5Multiple));
if(uglyNumber[i] == new2Multiple) multipleIndex2++;
if(uglyNumber[i] == new3Multiple) multipleIndex3++;
if(uglyNumber[i] == new5Multiple) multipleIndex5++;
}
return uglyNumber.back();
}
};