6.9-字典序的第K小数字

440. 字典序的第K小数字 - 力扣（LeetCode）)

• • 思路

    十叉树上求解第k小数字的解法

    总结：

    1.十叉树的字典序遍历

    2.逐层求解十叉树的子树节点个数的写法

    先序遍历这棵树，等价于从左到右遍历字典序列表。所以先序遍历访问到的第 k 个节点就是答案。

    从根节点的第一个儿子 1 开始。由于该节点被我们访问了，先把 k 减一。

    分类讨论：

    如果子树 1 的大小（节点个数）≤k，那么答案不在子树 1 中。把 k 减去子树大小，然后考虑下一个儿子 2，依此类推。 否则，答案在子树 1 中。首先访问 1 的儿子 10，把 k 减一。依次考虑 1 的儿子 10,11,12,…,19，计算子树大小，比较子树大小与 k 的大小关系，依此类推。 问：为什么判断条件是子树大小 ≤k 而不是 <k？

    答：因为当我们访问到子树根节点时，就把 k 减一了。这时再算子树大小，就把根节点重复统计了，所以是子树大小减一 <k，即子树大小 ≤k。

  • 代码

    class Solution {public int findKthNumber(int n, int k) {int root = 1;k--;while(k > 0) {int size = countSubTreeSize(n, root);if(k >= size) {k -= size;root++;} else {root *= 10;k--;}}return root;}public static int countSubTreeSize(int n, int root) {int size = 0;long left = root;long right = root + 1;while(left <= n) {size += Math.min(n + 1, right) - left;left *= 10;right *= 10; }return size;}
    }