---

1387. 将整数按权重排序

• 标签：记忆化搜索、动态规划、排序
• 难度：中等

题目链接

• 1387. 将整数按权重排序 - 力扣

题目大意

描述：给定三个整数 $lo$、$hi$ 和 $k$。定义一个整数的「权重」为将其变为 $1$ 所需要的步数，变换规则为：

• 如果 $x$ 是偶数，$x = x / 2$。
• 如果 $x$ 是奇数，$x = 3 \times x + 1$。

要求：将区间 $[lo, hi]$ 内的所有整数按照权重升序排序，如果权重相同则按数值升序。返回排序后第 $k$ 个数（从 $1$ 开始计数）。

说明：

• $1 \le lo \le hi \le 1000$。
• $1 \le k \le hi - lo + 1$。

示例：

• 示例 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：记忆化搜索 + 排序

1. 核心思想

定义函数 $power(x)$ 返回数字 $x$ 经过 Collatz 变换变为 $1$ 所需的步数。

直接递归计算会有大量重复计算（例如 $power(4)$ 和 $power(8)$ 都会计算 $power(4)$ 之后的过程）。用记忆化缓存加速。

2. 具体步骤

第 1 步：定义记忆化字典 $memo$，$memo[1] = 0$。

第 2 步：实现递归函数 $power(x)$：

• 如果 $x$ 在 $memo$ 中，直接返回。
• 如果 $x$ 是偶数，$power(x) = power(x / 2) + 1$。
• 如果 $x$ 是奇数，$power(x) = power(3 \times x + 1) + 1$。
• 将结果存入 $memo$ 并返回。

第 3 步：计算 $[lo, hi]$ 内每个数的权重，按（权重，数值）排序。

第 4 步：返回第 $k-1$ 个元素。

3. 举例说明

以 $lo = 12, hi = 15, k = 2$ 为例：

数字	变换过程	权重
12	12→6→3→10→5→16→8→4→2→1	9
13	13→40→20→10→5→16→8→4→2→1	9
14	14→7→22→11→34→17→52→26→13→...	17
15	15→46→23→70→35→106→53→160→...	17

排序结果（权重，数值）：$(9,12), (9,13), (17,14), (17,15)$。

第 $k=2$ 个是 $13$。

思路 1：代码

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {1: 0}

        def power(x):
            if x in memo:
                return memo[x]
            if x % 2 == 0:
                memo[x] = power(x // 2) + 1
            else:
                memo[x] = power(3 * x + 1) + 1
            return memo[x]

        nums = list(range(lo, hi + 1))
        nums.sort(key=lambda x: (power(x), x))

        return nums[k - 1]

思路 1：复杂度分析

• 时间复杂度：$O((hi-lo+1) \times \log(hi) + n \log n)$，$n = hi-lo+1$。计算权重需要递归深度约 $\log(hi)$，加上排序 $O(n \log n)$。
• 空间复杂度：$O(n + hi)$，记忆化缓存存储中间结果。

---

思路 2：迭代 + 缓存

也可以用迭代方式计算权重，但递归更简洁。注意 Collatz 猜想（$3n+1$ 问题）在本题数据范围内一定可以收敛到 $1$。