5350.将整数按权重排序 (Medium)*

题目描述*

我们将整数 x 的权重定义为按照下述规则将 x 变成 1 所需要的步数：

如果 x 是偶数，那么 x = x / 2
如果 x 是奇数，那么 x = 3 * x + 1

给你三个整数 lo， hi 和 k 。你的任务是将区间 [lo, hi] 之间的整数按照它们的权重升序排序，如果大于等于 2 个整数有相同的权重，那么按照数字自身的数值升序排序。请你返回区间 [lo, hi] 之间的整数按权重排序后的第 k 个数。

注意，题目保证对于任意整数 x （lo <= x <= hi），它变成 1 所需要的步数是一个 32 位有符号整数。

提示*

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

代码*

主要就是算出权重然后再排序，算的过程可以用 unordered_map 优化过程，避免重复计算。之后就用 K-th 的方法处理就行。

这里练习一下 lambda 表达式，要注意的是 lambda 表达式递归应该先声明，否则会报错。

class Solution {
public:
    int getKth(int lo, int hi, int k) {
        unordered_map<int, int> power;
        vector<pair<int, int>> res;
        power[1] = 0;
        function<int(int)> getWeight;
        getWeight = [&](int n)->int {
            if(power.find(n) == power.end()) {
                if(n & 1) {
                    power[n] = getWeight(3 * n + 1) + 1;
                }else {
                    power[n] = getWeight(n / 2) + 1;
                }
            }
            return power[n];
        };
        for(int i = lo; i <= hi; i++) {
            res.push_back(make_pair(i, getWeight(i)));
        }
        sort(res.begin(), res.end(), [](const auto& a, const auto& b) {
            if(a.second != b.second) {
                return a.second < b.second;
            }
            return a.first < b.first;
        });
        return res[k - 1].first;
    }
};

最后更新: July 23, 2022