题目大意：
将整数按权重排序
我们将整数 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 <= 10001 <= 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-解题思路分析/