用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]
让我们看下面的实现来更好地理解：
示例
#includeusing 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
以上是 用C++找出第n个丑数的程序 的全部内容， 来源链接： utcz.com/z/327632.html
