描述
给定整数n和k,找到按字典序排序的第k个最小整数,范围从1到n。
1 ≤ k ≤ n ≤ 1e9.
在线评测地址:领扣题库官网
样例1
输入:200,18
输出:114
解释:1,10,100,101,102,103,104,105,106,107,108,109,11,110,111,112,113,114,第十八个是114。
样例2
输入:13,2
输出:10
解释:按字典序排列顺序为 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], 所以第二小的数字为10。
考点
- 字符串
- 枚举
题解
字符串的构造类似于十叉树,用k减去子节点的个数,step表示以curr开头至curr+1开头间的字符串数量,step是否小于等于k,如果是,我们cur自增1,k减去step;如果不是,说明要求的数字在子节点中,我们此时cur乘以10,k自减1,以此类推,直到k为0推出循环,此时cur即为所求。
public class Solution {
/**
* @param n: a integer
* @param k: a integer
* @return: return a integer
*/
public int findKthNumber(int n, int k) {
int curr = 1;
k = k - 1;
while (k > 0) {
int steps = calSteps(n, curr, curr + 1);
if (steps <= k) { //如果不在当前层,减去steps
curr += 1;
k -= steps;
}
else { //说明在当前层,curr*10缩小搜索范围继续查找
curr *= 10;
k -= 1;
}
}
return curr;
}
//use long in case of overflow
public int calSteps(int n, long n1, long n2) { //计算curr开头和curr+1开头之间的字符串数量
int steps = 0;
while (n1 <= n) {
steps += Math.min(n + 1, n2) - n1; //每次加上当前的字符串数量
n1 *= 10; //每次均扩大10倍
n2 *= 10;
}
return steps;
}
}
更多题解参考:九章官网solution