在0~9的字典树(十叉树)上,首先计算以 cur 为前缀的小于等于n的节点个数有多少,即通过以 cur 为根找子树中小于等于 n 的节点个数
如果子树个数小于k,那么就在同一层向右平移1,
否则就跳到cur的一下层第一个子节点
点击查看代码
class Solution {
public int findKthNumber(int n, int k) {
int cur = 1;
-- k;
while(k > 0) {
int num = find(cur, n);
if(num <= k) {
k -= num;
++ cur;
} else {
cur *= 10;
-- k;
}
}
return cur;
}
public int find(int cur, int n) {
int num = 0;
long l = cur;
long r = cur;
while(l <= n) {
num += Math.min(r, n) - l + 1;
l = l * 10;
r = r * 10 + 9;
}
return num;
}
}