1387. Sort Integers by The Power Value¶
题目信息¶
- 题号:
1387
- 难度:
Medium
- 主题:
动态规划、记忆化、排序
- 原题:
- 重点:
幂值是按 Collatz 规则变到
1的步数;先按幂值升序,再按整数升序,返回第k个
题目重述¶
对正整数 x 反复执行:若为偶数则除以 2,若为奇数则变为 3x+1,直到得到 1。所需步数称为 x 的幂值。
把闭区间 [lo,hi] 内所有整数按幂值升序排序,幂值相同时按整数值升序排序。返回排序后的第 k 个整数,k 从一开始计数。
1 <= lo <= hi <= 1000,1 <= k <= hi-lo+1。
自建示例¶
幂值相同时使用数值作为次序:
输入:lo = 1, hi = 4, k = 3
输出:4
解释:1、2、3、4 的幂值分别为 0、1、7、2,排序为 [1,2,4,3]。
区间只有一个整数:
输入:lo = 7, hi = 7, k = 1
输出:7
解释:唯一候选直接返回。