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