假设我们必须找到第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]
让我们看下面的实现以更好地理解-
#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