原文链接: https://leetcode-cn.com/problems/sort-integers-by-the-power-value

英文原文

The power of an integer x is defined as the number of steps needed to transform x into 1 using the following steps:

• if x is even then x = x / 2
• if x is odd then x = 3 * x + 1

For example, the power of x = 3 is 7 because 3 needs 7 steps to become 1 (3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1).

Given three integers lo, hi and k. The task is to sort all integers in the interval [lo, hi] by the power value in ascending order, if two or more integers have the same power value sort them by ascending order.

Return the k-th integer in the range [lo, hi] sorted by the power value.

Notice that for any integer x (lo <= x <= hi) it is guaranteed that x will transform into 1 using these steps and that the power of x is will fit in 32 bit signed integer.

 

Example 1:

Input: lo = 12, hi = 15, k = 2
Output: 13
Explanation: The power of 12 is 9 (12 --> 6 --> 3 --> 10 --> 5 --> 16 --> 8 --> 4 --> 2 --> 1)
The power of 13 is 9
The power of 14 is 17
The power of 15 is 17
The interval sorted by the power value [12,13,14,15]. For k = 2 answer is the second element which is 13.
Notice that 12 and 13 have the same power value and we sorted them in ascending order. Same for 14 and 15.

Example 2:

Input: lo = 1, hi = 1, k = 1
Output: 1

Example 3:

Input: lo = 7, hi = 11, k = 4
Output: 7
Explanation: The power array corresponding to the interval [7, 8, 9, 10, 11] is [16, 3, 19, 6, 14].
The interval sorted by power is [8, 10, 11, 7, 9].
The fourth number in the sorted array is 7.

Example 4:

Input: lo = 10, hi = 20, k = 5
Output: 13

Example 5:

Input: lo = 1, hi = 1000, k = 777
Output: 570

 

Constraints:

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

中文题目

我们将整数 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 = 1, hi = 1, k = 1
输出：1

示例 3：

输入：lo = 7, hi = 11, k = 4
输出：7
解释：区间内整数 [7, 8, 9, 10, 11] 对应的权重为 [16, 3, 19, 6, 14] 。
按权重排序后得到的结果为 [8, 10, 11, 7, 9] 。
排序后数组中第 4 个数字为 7 。

示例 4：

输入：lo = 10, hi = 20, k = 5
输出：13

示例 5：

输入：lo = 1, hi = 1000, k = 777
输出：570

 

提示：

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

通过代码

高赞题解

题目分析

我们要按照权重为第一关键字，原值为第二关键字对区间 [lo, hi] 进行排序，关键在于我们怎么求权重。

方法一：递归

思路

记 $x$ 的权重为 $f(x)$，按照题意很明显我们可以构造这样的递归式：

$$
f(x) =
\left { \begin{aligned}
0 &, & x = 1 \
f(3x + 1) + 1 &, & x \bmod{2} = 1 \
f(\frac{x}{2}) + 1 &, & x \bmod{2} = 0
\end{aligned} \right .
$$

于是我们就可以递归求解每个数字的权重了。

代码

[sol1-C++]
class Solution {
public:
    int getF(int x) {
        if (x == 1) return 0;
        if (x & 1) return getF(x * 3 + 1) + 1;
        else return getF(x / 2) + 1;
    }

    int getKth(int lo, int hi, int k) {
        vector <int> v;
        for (int i = lo; i <= hi; ++i) v.push_back(i);
        sort(v.begin(), v.end(), [&] (int u, int v) {
            if (getF(u) != getF(v)) return getF(u) < getF(v);
            else return u < v;
        });
        return v[k - 1];
    }
};

[sol1-Java]
class Solution {
    public int getKth(int lo, int hi, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = lo; i <= hi; ++i) {
            list.add(i);
        }
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer u, Integer v) {
                if (getF(u) != getF(v)) {
                    return getF(u) - getF(v);
                } else {
                    return u - v;
                }
            }
        });
        return list.get(k - 1);
    }

    public int getF(int x) {
        if (x == 1) {
            return 0;
        } else if ((x & 1) != 0) {
            return getF(x * 3 + 1) + 1;
        } else {
            return getF(x / 2) + 1;
        }
    }
}

[sol1-Python3]
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]

复杂度分析

记区间长度为 $n$，等于 hi - lo + 1。

• 时间复杂度：这里的区间一定是 $[1, 1000]$ 的子集，在 $[1, 1000]$ 中权重最大数的权重为 $178$，即这个递归函数要执行 $178$ 次，所以排序的每次比较的时间代价为 $O(178)$，故渐进时间复杂度为 $O(178 \times n \log n)$。

• 空间复杂度：我们使用了长度为 $n$ 的数组辅助进行排序，同时再使用递归计算权重时最多会使用 $178$ 层的栈空间，故渐进空间复杂度为 $O(n + 178)$。

方法二：记忆化

思路

我们知道在求 $f(3)$ 的时候会调用到 $f(10)$，在求 $f(20)$ 的时候也会调用到 $f(10)$。同样的，如果单纯递归计算权重的话，会存在很多重复计算，我们可以用记忆化的方式来加速这个过程，即「先查表，再计算」和「先记忆，再返回」。我们可以用一个哈希映射作为这里的记忆化的「表」，这样保证每个元素的权值只被计算 $1$ 次。在 $[1, 1000]$ 中所有 $x$ 求 $f(x)$ 的值的过程中，只可能出现 $2228$ 种 $x$，于是效率就会大大提高。

代码如下。

代码

[sol2-C++]
class Solution {
public:
    unordered_map <int, int> f;

    int getF(int x) {
        if (f.find(x) != f.end()) return f[x];
        if (x == 1) return f[x] = 0;
        if (x & 1) return f[x] = getF(x * 3 + 1) + 1;
        else return f[x] = getF(x / 2) + 1;
    }

    int getKth(int lo, int hi, int k) {
        vector <int> v;
        for (int i = lo; i <= hi; ++i) v.push_back(i);
        sort(v.begin(), v.end(), [&] (int u, int v) {
            if (getF(u) != getF(v)) return getF(u) < getF(v);
            else return u < v;
        });
        return v[k - 1];
    }
};

[sol2-Java]
class Solution {
    Map<Integer, Integer> f = new HashMap<Integer, Integer>();

    public int getKth(int lo, int hi, int k) {
        List<Integer> list = new ArrayList<Integer>();
        for (int i = lo; i <= hi; ++i) {
            list.add(i);
        }
        Collections.sort(list, new Comparator<Integer>() {
            public int compare(Integer u, Integer v) {
                if (getF(u) != getF(v)) {
                    return getF(u) - getF(v);
                } else {
                    return u - v;
                }
            }
        });
        return list.get(k - 1);
    }

    public int getF(int x) {
        if (!f.containsKey(x)) {
            if (x == 1) {
                f.put(x, 0);
            } else if ((x & 1) != 0) {
                f.put(x, getF(x * 3 + 1) + 1);
            } else {
                f.put(x, getF(x / 2) + 1);
            }
        }
        return f.get(x);
    }
}

[sol2-Python3]
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]

复杂度分析

• 时间复杂度：平均情况下比较的次数为 $n \log n$，把 $2228$ 次平摊到每一次的时间代价为 $O(\frac{2228}{n \log n})$，故总时间代价为 $O(\frac{2228}{n \log n} \times n \log n) = O(2228)$。

• 空间复杂度：我们使用了长度为 $n$ 的数组辅助进行排序，哈希映射只可能存在 $2228$ 种键，故渐进空间复杂度为 $O(n + 2228)$。由于这里我们使用了记忆化，因此递归使用的栈空间层数会均摊到所有的 $n$ 中，由于 $n$ 的最大值为 $1000$，因此每一个 $n$ 使用的栈空间为 $O(\frac{2228}{1000}) \approx O(2)$，相较于排序的哈希映射需要的空间可以忽略不计。

统计信息

通过次数	提交次数	AC比率
10179	14682	69.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言