LEETCODE 440. K-th Smallest in Lexicographical Order解题思路分析

题目大意:

字典序的第K小数字

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

注意:1 ≤ k ≤ n ≤ 109

示例 :

输入: 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;
}

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

LEETCODE 440. K-th Smallest in Lexicographical Order解题思路分析》有2条回应

  1. Pingback引用通告: LEETCODE 60. Permutation Sequence 解题思路分析 - LEETCODE从零刷LEETCODE从零刷

发表评论

您的电子邮箱地址不会被公开。