在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作为输入

• ret：= 0

• 当n不是1时

• 如果n为奇数，则n：= n * 3 +1，否则n：= n / 2

• 增加ret 1

• 从主要方法

• 因为我在范围内

• 配对（getTurn(i)，i）

• 将温度插入ret

• 根据能力对对排序，否则按升序排序

• 返回对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