用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