用C++找出第n个丑数的程序
假设我们有一个数字n；我们必须找到第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
twoIdx:=2,ThreeIdx:=2,FiveIdx:=2
对于初始化i:=2，当i<=n时，更新（将i增加1），执行：
五:=v[fiveIdx]*5
（将五个Idx增加1）
三:=v[threeIdx]*3
（将threeIdx增加1）
二：=v[twoIdx]*2;
（将twoIdx增加1）
curr:=最少两个、三个和五个
v[i]:=当前
如果curr与两个相同，则：
如果curr与3相同，则：
如果curr与5相同，则：
返回v[n]
让我们看下面的实现来更好地理解：
示例
#include
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector 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(15));
}输入
15输出结果
24