class Solution {
public:
int getKth(int lo, int hi, int k) {
}
};
1387. 将整数按权重排序
我们将整数 x 的 权重 定义为按照下述规则将 x 变成 1 所需要的步数：
x 是偶数，那么 x = x / 2x 是奇数，那么 x = 3 * x + 1比方说，x=3 的权重为 7 。因为 3 需要 7 步变成 1 （3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1）。
给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重 升序排序 ，如果大于等于 2 个整数有 相同 的权重，那么按照数字自身的数值 升序排序 。
请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。
注意，题目保证对于任意整数 x （lo <= x <= hi） ，它变成 1 所需要的步数是一个 32 位有符号整数。
示例 1：
输入：lo = 12, hi = 15, k = 2 输出：13 解释：12 的权重为 9（12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1） 13 的权重为 9 14 的权重为 17 15 的权重为 17 区间内的数按权重排序以后的结果为 [12,13,14,15] 。对于 k = 2 ，答案是第二个整数也就是 13 。 注意，12 和 13 有相同的权重，所以我们按照它们本身升序排序。14 和 15 同理。
示例 2：
输入：lo = 7, hi = 11, k = 4 输出：7 解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。 按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。 排序后数组中第 4 个数字为 7 。
提示：
1 <= lo <= hi <= 10001 <= k <= hi - lo + 1原站题解
javascript 解法, 执行用时: 67 ms, 内存消耗: 51.1 MB, 提交时间: 2024-12-22 09:31:57
/**
* @param {number} lo
* @param {number} hi
* @param {number} k
* @return {number}
*/
const memo = {};
function dfs(i) {
if (i === 1) {
return 0;
}
if (memo[i] !== undefined) { // 之前计算过
return memo[i];
}
if (i % 2 === 1) {
memo[i] = dfs((i * 3 + 1) / 2) + 2;
} else {
memo[i] = dfs(i / 2) + 1;
}
return memo[i];
}
var getKth = function(lo, hi, k) {
const nums = Array.from({ length: hi - lo + 1 }, (_, i) => i + lo);
nums.sort((x, y) => {
const dx = dfs(x), dy = dfs(y);
return dx !== dy ? dx - dy : x - y;
});
return nums[k - 1];
};
cpp 解法, 执行用时: 28 ms, 内存消耗: 12.2 MB, 提交时间: 2024-12-22 09:31:37
unordered_map<int, int> memo;
int dfs(int i) {
if (i == 1) {
return 0;
}
auto it = memo.find(i);
if (it != memo.end()) { // 之前计算过
return it->second;
}
if (i % 2) {
return memo[i] = dfs((i * 3 + 1) / 2) + 2;
}
return memo[i] = dfs(i / 2) + 1;
}
class Solution {
public:
int getKth(int lo, int hi, int k) {
vector<int> nums(hi - lo + 1);
iota(nums.begin(), nums.end(), lo);
ranges::sort(nums, {}, [](int x) { return pair{dfs(x), x}; });
return nums[k - 1];
}
};
java 解法, 执行用时: 44 ms, 内存消耗: 44 MB, 提交时间: 2024-12-22 09:31:23
class Solution {
private static final Map<Integer, Integer> memo = new HashMap<>();
public int getKth(int lo, int hi, int k) {
Integer[] nums = new Integer[hi - lo + 1];
Arrays.setAll(nums, i -> i + lo);
Arrays.sort(nums, (x, y) -> {
int fx = dfs(x), fy = dfs(y);
return fx != fy ? fx - fy : x - y;
});
return nums[k - 1];
}
private int dfs(int i) {
if (i == 1) {
return 0;
}
if (memo.containsKey(i)) { // 之前计算过
return memo.get(i);
}
if (i % 2 == 1) {
memo.put(i, dfs((i * 3 + 1) / 2) + 2);
} else {
memo.put(i, dfs(i / 2) + 1);
}
return memo.get(i);
}
}
golang 解法, 执行用时: 24 ms, 内存消耗: 5.4 MB, 提交时间: 2022-11-25 21:47:30
type Weight struct {
num int
weight int
}
func getWeight(num int) int {
res := 0
for num != 1 {
if num % 2 == 0 {
num /= 2
} else {
num = num * 3 + 1
}
res++
}
return res
}
func getKth(lo int, hi int, k int) int {
s := []*Weight{}
for i := lo; i <= hi; i++ {
weight := getWeight(i)
s = append(s, &Weight{num: i, weight: weight})
}
sort.SliceStable(s, func(i, j int) bool {
return s[i].weight < s[j].weight
})
return s[k - 1].num
}
golang 解法, 执行用时: 16 ms, 内存消耗: 5.3 MB, 提交时间: 2022-11-25 21:46:11
func getKth(lo int, hi int, k int) int {
nums:=[]*item{}
for i:=lo;i<=hi;i++{
w:=weight(i)
nums = append(nums,&item{weight: w,num: i})
}
sort.Slice(nums,func(i,j int) bool{
if nums[i].weight==nums[j].weight{
return nums[i].num<nums[j].num
}
return nums[i].weight<nums[j].weight
})
return nums[k-1].num;
}
type item struct{
weight int
num int
}
func weight(x int) int{
w:=0
for x>1{
if x%2==0{
x=x/2
}else{
x = 3*x+1
}
w++
}
return w
}
python3 解法, 执行用时: 156 ms, 内存消耗: 27.9 MB, 提交时间: 2022-11-25 21:39:02
class Solution:
def getKth(self, lo: int, hi: int, k: int) -> int:
f = {1: 0}
def getF(x):
if x in f:
return f[x]
f[x] = (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1
return f[x]
v = list(range(lo, hi + 1))
v.sort(key=lambda x: (getF(x), x))
return v[k - 1]
python3 解法, 执行用时: 760 ms, 内存消耗: 15.1 MB, 提交时间: 2022-11-25 21:38:32
class Solution:
def getKth(self, lo: int, hi: int, k: int) -> int:
def getF(x):
if x == 1:
return 0
return (getF(x * 3 + 1) if x % 2 == 1 else getF(x // 2)) + 1
v = list(range(lo, hi + 1))
v.sort(key=lambda x: (getF(x), x))
return v[k - 1]