数据结构
网络
关系型数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究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
从主方法
对于 I 在 lo 到 hi 的范围内
创建一个 (getTurn(i), i) 对
将 temp 插入 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
更新于：2020-04-29
191 次查看
广告