将整数按权重排序

标签: 记忆化搜索 动态规划 排序

难度: Medium

我们将整数 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] 之间的整数按照它们的权重 升序排序 ，如果大于等于 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 <= 1000
  • 1 <= k <= hi - lo + 1

Submission

运行时间: 47 ms

内存: 16.2 MB

@cache
def f(x: int) -> int:
    ans = 0
    while x != 1:
        if x % 2 == 0:
            x //= 2
        else:
            x = 3 * x + 1
        ans += 1
    return ans


class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted(range(lo, hi + 1), key=f)[k - 1]

Explain

题解的核心思想是使用动态规划来计算每个整数x的权重，即变成1所需的步骤数。这里利用了缓存装饰器@cache，它存储每个已计算过的整数的权重，以避免重复计算。函数f(x)负责计算一个给定的x的权重。如果x是偶数，则x除以2；如果x是奇数，则变为3*x+1，重复此过程直到x变为1。主要的函数getKth()使用这个计算权重的函数作为排序键值，对区间[lo, hi]中的所有整数进行排序，并返回第k小的整数。

时间复杂度: O(n log n log n)

空间复杂度: O(n)

@cache
def f(x: int) -> int:
    # 初始化步数为0
    ans = 0
    # 当x不等于1时，循环继续
    while x != 1:
        # 如果x是偶数，则x变为x除以2
        if x % 2 == 0:
            x //= 2
        # 如果x是奇数，则x变为3*x + 1
        else:
            x = 3 * x + 1
        # 每执行一次操作步数增加1
        ans += 1
    return ans

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        # 对区间[lo, hi]内的整数按照权重排序，返回第k个整数
        return sorted(range(lo, hi + 1), key=f)[k - 1]

Explore

在题解中使用 @cache 装饰器是为了缓存函数f(x)的结果。这种方法可以避免对相同的整数x重复计算权重，特别是在计算过程中经常会遇到重复的数值。例如，在递归过程中，不同的起始值可能会导致相同的中间结果，使用缓存可以直接从存储中读取这些中间结果的权重，而不需要再次进行计算。这大大提高了算法的效率，尤其是在处理大范围整数时，可以显著减少计算时间。

函数f(x)依据的是著名的Collatz猜想（3x + 1猜想），该猜想虽然未被严格证明，但广泛的数学实验表明，对任何正整数应用此过程，最终都会收敛至1。尽管对于非常大的整数，数值在增长到一定阶段后可能会出现很大的值，但根据猜想，这些值最终都将回归到较小的数值，并最终达到1。因此，在目前的理解下，函数f(x)不会进入无限循环，这基于对Collatz猜想的普遍接受和验证。

题解中没有特别提到关于整数溢出的处理措施。在Python中，整数类型支持长整数计算，因此理论上可以处理非常大的数而不会发生溢出。然而，在其他语言中，如C++或Java，这种3*x + 1的操作确实可能导致整数溢出，特别是当x的值非常大时。在这种情况下，可能需要采用更大范围的整数类型或进行特定的溢出检查来确保算法的正确性和安全性。