C++の醜い数II

n番目の醜い数を見つけなければならないので、それを見つけることができるメソッドを定義する必要があるとします。醜い数は素因数が2、3、5しかない数であることがわかっているので、10番目の醜い数を見つけたい場合、最初のいくつかの醜い数は1、2、3であるため、12になります。 4、5、6、8、9、10、12

これを解決するには、次の手順に従います-

• サイズn+1の配列vを作成します

• n =1の場合、1を返します

• 2：=2、3=3および5=5、towIndex：=2、threeIndex：=2およびfiveIndex：=2

• 2からnの範囲のiの場合

  • curr：=2、3、5の最小値

  • v [i]：=curr

  • curr =2の場合、2：=v [twoIndex] * 2、twoIndexを1増やします

  • curr =3の場合、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