資料結構
網路
關係型資料庫管理系統
作業系統
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 次檢視
廣告