264. 丑数II
编写一个程序，找出第 n 个丑数。
丑数就是只包含质因数 2, 3, 5 的正整数。
示例:
1
2
3
4
5
6
| 输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
1 是丑数。
n 不超过1690。
|
思路：动态规划
每次都找已经存在的数中 * 2或 * 3 或 * 5之后较小的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public:
int nthUglyNumber(int n) {
vector<int> res(1, 1);
int i2 = 0, i3 = 0, i5 = 0, i = 1;
while(i++ < n) {
int tmp = min(2 * res[i2], min(3 * res[i3], 5 * res[i5]));
res.push_back(tmp);
if(tmp == 2 * res[i2]) i2++;
if(tmp == 3 * res[i3]) i3++;
if(tmp == 5 * res[i5]) i5++;
}
return res.back();
}
};
|