440_字典序的第K小数字

难度：困难

题目

给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。

示例

示例一：

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

示例二：

输入: n = 1, k = 1
输出: 1

提示

  • $1 <= k <= n <= 10^9$

解题

image.png

可以参照上图来理解

  1. 初始化前缀为 1，计算以 1 为前缀的所有子树节点树木，如果小于 k ，说明当前子树的节点数不够，向右移动变为 2，如果大于 k ，说明答案就在当前根节点的子树节点，向下移动 变为 10
  2. k 减去已经遍历过的节点个数，以当前为根节点，直到 k=0

第一层节点数为： 1 = nextPrefix - prefix; | 2 - 1
第二层的节点数为10 = nextPrefix - prefix; | (2 * 10) - (1 * 10)
…

由于最后一层可能出现结点不满的情况，所以要取 总结点数 - prefix 与 nextPrefix - prefix的最小值，即：

第n层的节点数为：Math.min (k - prefix , nextPrefix - prefix); | k - (1 * 10^n) 、(n * 10^n) - (1 * 10^n)

于是对于每一层的节点数，直接用一个式子表示：Math.min (k - prefix , nextPrefix - prefix)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
public int findKthNumber(int n, int k){
    // 从根节点下面的第一个节点 1 开始遍历
    long curr = 1;
    // 从 1 出发后按字典序从小到大的顺序走 k-1 步就是 字典序第 k 小的数字
    k -= 1;
    while (k>0){
        // 得到以当前节点为根的所有子树节点数目
        int node = getCount(n,curr);
        // 如果 k 大于当前根节点下所有子树节点的数目，就向右侧移动 -> 2 -> 3 -> 4 ...
        if (k>=node){
            // 减去已经遍历的个数
            k-=node;
            // 根节点右移
            curr++;
        }
        // 如果 k 小于当前根节点下子树节点数目，说明答案就在当前根节点的子树节点中
        else{
            // 减去根节点的数量 1
            k -= 1;
            // 将根节点移动到下一层(每层有 10 个节点)
            curr *= 10;
        }
    }
    // 最终 k=0 时,就找到了答案
    return (int)curr;
}

// 计算以 curr 为根的子树节点数目，所有节点值必须 <= n
public int getCount(int n, long curr){
    // 记录子树中的全部节点数目
    long totalCounts = 0;
    // 当前节点右侧节点的值
    long next = curr + 1;
    while (curr<=n){
        // 取整行节点的个数，可能全满，也可能是叶子节点，没有满
        totalCounts += Math.min(n-curr+1, next - curr);
        next *=10;
        curr *=10;
    }
    return (int)totalCounts;
}