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 =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));
}

C++의 못생긴 숫자 II

예시(C++)

입력

출력