C ++中的丑陋数字II
假设我们必须找到第n个丑数，所以我们必须定义一个可以找到它的方法。我们知道丑陋的数字就是那些素数只有2、3和5的数字。因此，如果我们想找到第10个丑陋的数字，那就是12，因为前几个丑陋的数字是1、2、3，4，5，6，8，9，10，12
为了解决这个问题，我们将遵循以下步骤-
制作大小为n+1的数组v
如果n=1，则返回1
两个：=2，三个=3和五个=5，towIndex：=2，threeIndex：=2和FiveIndex：=2
对于我2到n
curr：=2、3和5中的最小值
v[i]：=curr
如果curr=2，则两个：=v[twoIndex]*2，将twoIndex增加1
如果curr=3，则三个：=v[threeIndex]*3，将threeIndex增加1
如果curr=5，则5：=v[fiveIndex]*3，将FiveIndex增加1
返回v[n]
例子（C++）
让我们看下面的实现以更好地理解-
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector <int> v(n + 1);
if(n == 1){
return 1;
}
int two = 2, three = 3, five = 5;
int twoIdx = 2;
int threeIdx = 2;
int fiveIdx = 2;
for(int i = 2; i <= n; i++){
int curr = min({two, three, five});
v[i] = curr;
if(curr == two){
two = v[twoIdx] * 2;;
twoIdx++;
}
if(curr == three){
three = v[threeIdx] * 3;
threeIdx++;
}
if(curr == five){
five = v[fiveIdx] * 5;
fiveIdx++;
}
}
return v[n];
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(10));
}输入值
10
输出结果
12