C++の電力値で整数を並べ替える

整数xの累乗は、次の手順を使用してxを1に変換するために必要な手順数として定義されていることがわかっています-

• xが偶数の場合、x =x / 2

• xが奇数の場合、x =3 * x + 1

たとえば、3は7ステップを使用して1になるため（3→10→5→16→8→4→2→1）、x=3の累乗は7になります。したがって、いくつかの整数lo、hi、およびkがある場合。区間[lo、hi]のすべての整数を、累乗値の昇順で並べ替える必要があります。ここで、2つ以上の整数の累乗値が同じである場合は、昇順で並べ替えます。累乗値でソートされた範囲[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を入力として受け取ります

• ret：=0

• nは1ではありません

  • nが奇数の場合、n：=n * 3 + 1、それ以外の場合、n：=n / 2

  • retを1増やします

• メインメソッドから

• 私はloからhiの範囲にいます

  • ペアを作る（getTurn（i）、i）

  • 温度をretに挿入

• パワーに基づいてペアを並べ替えます。それ以外の場合は昇順で並べ替えます

• ペアの2番目の値を返す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

出力

13