関小君刷题记

题目大意：

字典序的第K小数字

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 10⁹。

示例 :

输入: n: 13   k: 2 
输出: 10 
解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=440

解题思路：

这道题确实够得上Hard难度。我最初的想法是暴力解，按照字典顺序将前k个数字排序出来，然后再看第k个数字是什么，不过看了一眼题目的数字范围大小，果断放弃了。接下来说下标准的思路。

首先考虑下什么是字典顺序，比如1到100的数字中，1之后是10，10之后是100，100之后应是11。总结来说，按照字典排序的话，1和2之间的应该包含所有以1开头的1位数（只有1），以1开头的2位数（10 – 19），以及小于等于100的以1开头的三位数（只有100）。2和3之间的所有数也同理。这样的一个关系我们可以用十叉树来思考，对于任意一个数字，它的下面一层都会包含最多10个子节点。比如在n无限大的情况下，1的下面有10 – 19十个节点。10的下面有100 – 109十个节点。再比如55的下面有550 – 559十个节点。不过考虑到n是有限大的数字，所以并非每个数字节点下都能包含10个子节点，比如本题给出的例子，当n为13时，1的子节点只有10，11，12和13四个子节点。大家可以自己画一下图来加深记忆。

那么，当建立了十叉树思想之后，应如何解题呢？大体思路如下：

1. 写一个方法getChildrenCount()，用于计算出当前节点下存在多少个子节点。（后面讨论）
2. 数字按照字典排序，第一位肯定是1，所以我们从1开始着手，看1的下面存在多少个子节点数childrenCount。
3. 题目是求第k位的数字，如果当k 大于 1的childrenCount时，说明了第k位一定在1的所有子节点之后，我们应该在2子节点中继续查找。这属于横向移动，1移动到2，跨越了1本身以及1的所有子节点的个数，因此k值变为：k = k – childrenCount – 1，利用新的k值与2的所有子节点个数继续进行比较，直到k小于等于当前节点所有子节点个数为止。
4. 如果当k小于等于childrenCount时，说明第k位就在当前数字的十叉树目录下面，比如当前节点为1，那么1的下一层子节点包含10 – 19十个子节点，按照顺序，我们将1移动到其第一个子节点10，这属于纵向移动，任何节点与之第一个子节点之间的距离是1，因此k值应变为：k = k – 1。接下来计算出10一共包含多少个子节点childrenCount，然后在按照上面3的思路继续循环。（如果k大于childrenCount，移动至11，否则移动至100）

思路大概讲清楚了，接下来看看剩下的一个问题，如何计算某一数字节点下包含多少个子节点的问题。其实这个并不难，文章开头已经说了，在不考虑n大小的情况下，任意一个数字下面都有10个子节点，比如1下面是10 – 19，那么也就是说，从顶点开始，每向下走一层，子节点数量会是上一层的十倍。比如：

[1]
[10] [11] [12] ... [19] // 10个
[100] [101]... [109] ... ... [190] [191] ... [199] // 100个
[1000] [1001] ... ... [1999] // 1000个

但是题目给出的n是有取值范围的，因此任何一个子节点不可以大于n，比如当n为1200时，上面的例子就变为了：

[1]
[10] [11] [12] ... [19] // 10个
[100] [101]... [109] ... ... [190] [191] ... [199] // 100个
[1000] [1001] ... ... [1200] // 201个，也就是说120的子节点只有1200一个

那么，第4层的节点数就不是1000而是201个，201的计算方法是当前层理论节点数1000减去当前层理论上最大数1999与实际最大数1200的差（799）

1000 - (1999 - 1200) = 201;

最后看下完整代码：

public int findKthNumber(int n, int k) {
    long current = 1; // 从字典第一位1开始查找
    k--; // 除去第一位
    // 当k变为0时，当前节点即是结果
    while (k > 0) {
        // 取得当前节点的所有子节点数量
        int childrenCount = getChildrenCount(current, n);
        // 如果k小于等于当前节点的所有子节点数，说明第k个数在当前节点的树目录中
        if (k <= childrenCount) {
            // 将当前节点纵向向下移动一层，消费掉k的一位
            k--;
            // 向下纵向移动，当前数变为原来十倍
            current *= 10;
        } 
        // 如果k大于当前节点的所有子节点数，说明第k位在当前节点的所有子节点之后
        else if (k > childrenCount) {
            // 移动到树的右边一个节点，消费掉2个节点间的子节点数量
            k -= (childrenCount + 1);
            // 向右移动，当前数变为原来加一
            current++;
        }
    }
    return (int) current;
}
// 取得当前节点的所有子节点数
private int getChildrenCount(long current, int n) {
    long childrenCount = 0; // 所有子节点数
    long maxChild = current; // 当前层理论最大子节点的值
    long maxChildrenCount = 1; // 当前层理论最多节点数量
    while (current * 10 <= n) {
        // 每向下一层，当前层的子节点数是上一层的10倍，再加上之前层的子节点为总数
        childrenCount = childrenCount + maxChildrenCount * 10;
        // 当前层理论最多节点数量乘以10，为了下一层计算使用
        maxChildrenCount *= 10;
        // 当前层理论最大子节点的值为为上一层最大值乘以10再加上9
        maxChild = maxChild * 10 + 9;
        // 如果理论最大值大于n，计算出实际子节点数量
        if (maxChild > n) {
            childrenCount = childrenCount - (maxChild - n);
            break;
        }
        // 向下移动一层，当前数变为原来10倍
        current *= 10;
    }
    return (int) childrenCount;
}

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-440-k-th-smallest-in-lexicographical-order解题思路分析/