1. 题目
2. 解答
字典序排数可以看做是第一层节点分别为 1-9 的十叉树，然后我们在树上找到第 K 小的数字即可。因此，我们需要分别统计以 1-9 为根节点的每个树的节点个数。如果 K 小于当前树的节点个数，那么第 K 小的数字即在当前树中，我们进入子树继续查找；如果 K 大于当前树的节点个数，那么我们需要查找后面树中第 (K - 当前树节点) 小的数字。
其中，比较关键的步骤就是统计树中的节点个数，我们按照逐层统计的方法来进行，详见下图。
- 首先我们初始化 cur = 1
- 然后我们让 left = cur，right = cur + 1，此时 right-left 就是第一棵树第一层的节点个数
- 接下来 left *= 10, right *= 10，这样就进入到了第二层，此时 right-left 就是第二层的节点个数，以此类推直到 left > n
- 但如果我们是统计 109 以内的字典序，进入第三层时，right 不能指向 200 而只能指向 109，此时 right-left+1 才是当前层的节点个数
假设我们统计完第一棵树的节点数为 node_num
- 如果 K >= node_num，我们需要继续向后查找，在后面的树中查找第 K-node_num 小的数字，也即更新 cur += 1
- 如果 K < node_num，说明第 K 小的数字在子树中，我们需要进入子树继续向下查找，也即更新 cur *= 10
最后当 K=0 时，cur 指向的值即为所求。
class Solution {
public:
int findKthNumber(int n, int k) {
int cur = 1;
k--;
while (k > 0)
{
long long left = cur;
long long right = cur + 1;
int node_num = 0;
while (left <= n) // 统计树中每一层的节点个数
{
node_num += min(right, (long long)(n+1)) - left;
left *= 10;
right *= 10;
}
if (node_num <= k) // 向后查找
{
k -= node_num;
cur++;
}
else // 进入子树查找
{
k--;
cur *= 10;
}
}
return cur;
}
};
获取更多精彩，请关注「seniusen」!