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] 中的所有整数，如果两个或多个整数具有相同的幂值，则按升序排列它们。

返回区间 [lo, hi] 中按幂值排序的第 k 个整数。

注意，对于任何整数 x (lo <= x <= hi)，保证 x 将使用这些步骤转换为 1，并且 x 的幂值适合 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]。
排序数组中的第四个数字是 7。

约束：

  • 1 <= lo <= hi <= 1000
  • 1 <= k <= hi - lo + 1

解题思路

这是一道经典的记忆化搜索+排序问题。

思路分析：

  1. 计算幂值（记忆化搜索）：对于每个数字，我们需要按照给定规则计算到达1的步数。由于计算过程中会出现重复的中间结果，使用记忆化搜索可以大大提升效率。例如计算12的幂值时，会经过6、3等中间值，这些值的幂值可以被其他数字复用。

  2. 排序策略：计算出区间[lo, hi]内所有数字的幂值后，需要按照以下规则排序：

    • 主要按幂值升序排列
    • 幂值相同时，按数字本身升序排列

  3. 返回第k个元素：排序完成后直接返回第k-1个元素（0索引）。

算法步骤：

  1. 使用哈希表memo存储已计算的幂值
  2. 实现递归函数计算幂值，利用记忆化避免重复计算
  3. 生成区间内所有数字及其幂值的配对
  4. 按照排序规则对配对进行排序
  5. 返回第k个数字

推荐解法：记忆化搜索，时间复杂度低，代码简洁易懂。

代码实现

class Solution {
public:
    unordered_map<int, int> memo;
    
    int getPower(int x) {
        if (x == 1) return 0;
        if (memo.count(x)) return memo[x];
        
        int result;
        if (x % 2 == 0) {
            result = 1 + getPower(x / 2);
        } else {
            result = 1 + getPower(3 * x + 1);
        }
        
        return memo[x] = result;
    }
    
    int getKth(int lo, int hi, int k) {
        vector<pair<int, int>> nums;
        
        for (int i = lo; i <= hi; i++) {
            nums.push_back({getPower(i), i});
        }
        
        sort(nums.begin(), nums.end());
        
        return nums[k - 1].second;
    }
};

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        memo = {}
        
        def getPower(x):
            if x == 1:
                return 0
            if x in memo:
                return memo[x]
            
            if x % 2 == 0:
                result = 1 + getPower(x // 2)
            else:
                result = 1 + getPower(3 * x + 1)
            
            memo[x] = result
            return result
        
        nums = []
        for i in range(lo, hi + 1):
            nums.append((getPower(i), i))
        
        nums.sort()
        
        return nums[k - 1][1]

public class Solution {
    private Dictionary<int, int> memo = new Dictionary<int, int>();
    
    private int GetPower(int x) {
        if (x == 1) return 0;
        if (memo.ContainsKey(x)) return memo[x];
        
        int result;
        if (x % 2 == 0) {
            result = 1 + GetPower(x / 2);
        } else {
            result = 1 + GetPower(3 * x + 1);
        }
        
        memo[x] = result;
        return result;
    }
    
    public int GetKth(int lo, int hi, int k) {
        List<(int power, int num)> nums = new List<(int, int)>();
        
        for (int i = lo; i <= hi; i++) {
            nums.Add((GetPower(i), i));
        }
        
        nums.Sort((a, b) => a.power == b.power ? a.num.CompareTo(b.num) : a.power.CompareTo(b.power));
        
        return nums[k - 1].num;
    }
}

var getKth = function(lo, hi, k) {
    const memo = new Map();
    
    function getPower(x) {
        if (memo.has(x)) return memo.get(x);
        
        let original = x;
        let steps = 0;
        
        while (x !== 1) {
            if (x % 2 === 0) {
                x = x / 2;
            } else {
                x = 3 * x + 1;
            }
            steps++;
        }
        
        memo.set(original, steps);
        return steps;
    }
    
    const nums = [];
    for (let i = lo; i <= hi; i++) {
        nums.push([i, getPower(i)]);
    }
    
    nums.sort((a, b) => {
        if (a[1] === b[1]) {
            return a[0] - b[0];
        }
        return a[1] - b[1];
    });
    
    return nums[k - 1][0];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型时间复杂度空间复杂度
总体O(n log n + n·m)O(m)

说明：

  • n = hi - lo + 1（区间内数字个数）
  • m = 记忆化过程中遇到的不同数字个数
  • 时间复杂度：计算所有幂值O(n·m)，排序O(n log n)
  • 空间复杂度：记忆化哈希表O(m)，存储结果数组O(n)

相关题目