C++의 거듭제곱 값으로 정수 정렬

정수 x의 거듭제곱은 다음 단계를 사용하여 x를 1로 변환하는 데 필요한 단계 수로 정의된다는 것을 알고 있듯이 -

x가 짝수이면 x =x / 2
x가 홀수이면 x =3 * x + 1

예를 들어 x =3의 거듭제곱은 7입니다. 3은 7단계를 거쳐 1이 되기 때문입니다(3 → 10 → 5 → 16 → 8 → 4 → 2 → 1). 따라서 정수 lo, hi 및 k가 있는 경우. [lo, hi] 구간의 모든 정수를 거듭제곱 값으로 오름차순으로 정렬해야 합니다. 이제 둘 이상의 정수가 동일한 거듭제곱 값을 가지면 오름차순으로 정렬합니다. 거듭제곱 값으로 정렬된 [lo, hi] 범위에서 k번째 정수를 찾아야 합니다.

예를 들어, 입력이 lo =12, hi =15 및 k =2와 같으면 출력은 13이 됩니다. 이는 12의 거듭제곱이 9이고 13의 거듭제곱이 9이기 때문입니다. 14의 경우 이것은 17이고, 15의 경우 17이므로 정렬된 시퀀스는 [12,13,14,15]이고 k =2인 경우 요소는 13입니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

getTurn 메소드를 정의하십시오. 이것은 n을 입력으로 사용합니다.
렛 :=0
n이 1이 아닌 동안
- n이 홀수이면 n :=n * 3 + 1, 그렇지 않으면 n :=n / 2
- ret 1 증가
주요 방법에서
나는 범위 lo에서 hi까지
- 쌍을 이루다 (getTurn(i), i)
- ret에 temp 삽입
거듭제곱을 기준으로 쌍을 정렬하고, 그렇지 않으면 오름차순으로 정렬
쌍 ret[k - 1]
의 두 번째 값을 반환합니다.

예시(C++)

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   vector < pair <int, int> > ret;
   static bool cmp(pair <int, int>& a, pair <int, int>& b){
      return a.first == b.first ? a.second < b.second : a.first < b.first;
   }
   int getTurn(int n){
      int ret = 0;
      while(n != 1){
         if(n & 1){
            n = n * 3 + 1;
         }
         else n >>= 1;
            ret ++;
      }
      return ret;
   }
   int getKth(int lo, int hi, int k) {
      for(int i = lo; i <= hi; i++){
         pair <int, int> temp;
         temp.first = getTurn(i);
         temp.second = i;
         ret.push_back(temp);
      }
      sort(ret.begin(), ret.end(), cmp);
      return ret[k - 1].second;
   }
};
main(){
   Solution ob;
   cout << (ob.getKth(12, 15, 2));
}

입력

12
15
2