[LeetCode] 每日一题 1387. 将整数按权重排序

题目链接

题目描述

我们将整数 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

题解

解题思路

该题目的核心是根据数值的“权重”进行排序，然后返回第 k 个数值。权重的计算通过递归进行。为了最优化解决，我们可以使用以下方法解决：

1. 预算权重值：使用一个记忆化的方式（通过一个存储器来记录前面的结果）来减少重复计算。

2. 排序解决前 k 个元素：可以使用一个优先队列（PriorityQueue），根据权重值和数值进行排序。

代码实现

class Solution {
    // 记忆化存储器
    Map<Integer, Integer> map = new HashMap<>();

    public int getKth(int lo, int hi, int k) {
        // 优先队列根据权重和值进行排序
        PriorityQueue<Integer> queue = new PriorityQueue<>((e1, e2) -> {
            if (getW(e1) == getW(e2)) {
                return e1 - e2;
            }
            return getW(e1) - getW(e2);
        });

        // 将 [lo, hi] 的值加入队列
        for (int i = lo; i <= hi; i++) {
            queue.offer(i);
        }

        // 选取排序后的第 k 个元素
        int ans = 0;
        while (k-- > 0) {
            ans = queue.poll();
        }
        return ans;
    }

    // 计算权重值（带记忆化）
    private int getW(int n) {
        if (n == 1) {
            return 0;
        }
        if (map.containsKey(n)) {
            return map.get(n);
        }
        int w = 1;
        if (n % 2 == 0) {
            w += getW(n / 2);
        } else {
            w += getW(3 * n + 1);
        }
        map.put(n, w);
        return w;
    }
}

关键点解释

• 记忆化解决重复计算问题：元素的权重可能被多次调用，因此使用 Map 记忆已经计算过的结果，减少计算重复。

• 优先队列解决排序：通过优先队列，根据权重和值进行实时排序，加速计算。

• 比较策略：在 PriorityQueue 中，如果权重相同，使用数值的升序排序；如果权重不同，根据权重升序排序。

总结

该解法通过记忆化和优先队列的设计，最大突出是在保证正确性的同时，最大限度地提高了计算效率。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。