LEETCODE 1387. Sort Integers by The Power Value 解题思路分析

题目大意:

将整数按权重排序

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

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=1387

解题思路分析:

本题没有什么好的办法,我们必须先计算出每一个数字的权重值,然后再排序找到第k个。解题时,我们可以使用PriorityQueue对数据进行排序,Queue中每一个元素是一个数组,分别记录每一个数字以及他的权重值,在对Queue内数据进行排序时,先按照权重值升序排序,如果权重值相同,再按照数字升序排序。最后取出Queue中的第k个元素的数字即是返回结果。

另外在计算权重值时,我们可以使用记忆数组来优化算法,避免更多的重复计算,举个例子,比如我们计算过12的权重值为9,那么当我们再计算24的权重时,由于24是偶数,我们先将它除以2得到12,此时已知12的权重是9,因此24的权重是9加1等于10。

实现代码:

// 记忆数组
Map<Integer,Integer> memo=new HashMap<>();
public int getKth(int lo, int hi, int k) {
    // 排序用的Queue
    PriorityQueue<int[]> q=
        new PriorityQueue<>((a,b)->a[1]-b[1]==0?a[0]-b[0]:a[1]-b[1]);
    // 计算每个数字的权重值
    for(int num=lo;num<=hi;num++){
        // 将每个数字以及他的权重值加入到Queue中
        q.offer(new int[]{num,getPower(num)});
    }
    // 先取出前k-1个数据
    for(int i=0;i<k-1;i++) q.poll();
    // 返回第k个数字
    return q.poll()[0];
}
// 计算num的权重值
int getPower(int num){
    // 如果num是1,返回0
    if(num==1) return 0;
    // 如果记忆数组中存在当前数字的权重,直接返回
    if(memo.containsKey(num)) return memo.get(num);
    // 权重值为初始为1
    int res=1;
    // 如果是偶数,将当前数字除以2,递归求解
    if(num%2==0) res+=getPower(num/2);
    // 如果是奇数,将当前数字乘以3再加一,递归求解
    else res+=getPower(num*3+1);
    // 将当前数字的权重保存至记忆数组
    memo.put(num,res);
    return res;
}

本题解法执行时间为40ms。

Runtime: 40 ms, faster than 90.95% of Java online submissions for Sort Integers by The Power Value.

Memory Usage: 41.3 MB, less than 100.00% of Java online submissions for Sort Integers by The Power Value.Next challenges:

本网站文章均为原创内容,并可随意转载,但请标明本文链接
本文链接: https://leetcode.jp/leetcode-1387-sort-integers-by-the-power-value-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , , 标签。将固定链接加入收藏夹。

发表评论

电子邮件地址不会被公开。