题目描述
编写一个程序,找出第 n 个丑数。
丑数就是质因数只包含 2, 3, 5 的正整数。
示例:
输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
class Solution {
public:
int nthUglyNumber(int n) {
//用三个指针分别指向3个类型的丑数
//1. 2*(1 2 3 4 5 6 8 10)(2的丑数倍)
//2. 3*(1 2 3 4 5 6 8 10)(3的丑数倍)
//3. 5*(1 2 3 4 5 6 8 10)(5的丑数倍)
//所以原来的丑数可以作为索引 处理整个数据
vector<int> ugly(n,0);
ugly[0] = 1;
int i_2,i_3,i_5;
i_2 = i_3 = i_5 = 0;
for(int i = 1;i<n;i++){
int val = min(min(ugly[i_2]*2,ugly[i_3]*3),ugly[i_5]*5);
if(val==ugly[i_2]*2)i_2++;
if(val==ugly[i_3]*3)i_3++;
if(val==ugly[i_5]*5)i_5++;
ugly[i] = val;
}
return ugly[n-1];
}
};