0440. K-th Smallest in Lexicographical Order
============================================
题目信息
--------
:题号: 0440
:难度: Hard
:主题: 整数范围、十进制字典序、一基排名、第 ``k`` 个数
:原题: `LeetCode 0440 `_
:重点: 排序对象是整数 ``1..n`` 的十进制表示、按字符串字典序比较、``k`` 从 1 开始、返回整数本身
题目重述
--------
给定整数 ``n`` 和 ``k``,把所有整数 ``1, 2, ..., n`` 按其十进制字符串的字典序排列,返回排列中的第 ``k`` 个整数。
字典序按字符逐位比较,例如 ``10``、``100``、``101`` 都排在 ``2`` 之前。``n`` 位于 ``[1, 10^9]``,``k`` 位于 ``[1, n]``。排名采用一基编号,只返回对应整数,不需要构造或返回完整排列。
自建示例
--------
排名跨过前缀 1 的整棵分支:
.. code-block:: text
输入:n = 25,k = 13
输出:20
解释:前 13 个数依次为 1、10、11、12、13、14、15、16、17、18、19、2、20,因此第 13 个是 20。
全部都是一位数:
.. code-block:: text
输入:n = 9,k = 7
输出:7
解释:1 到 9 的字典序与数值顺序相同,第七个整数为 7。
前缀子树计数与跳过
------------------
把整数看成十叉字典树中的节点:``1`` 的下一层是 ``10`` 到 ``19``,``2`` 的下一层是 ``20`` 到 ``29``。字典序遍历一棵子树时,会先访问前缀本身,再访问所有更长的后缀,因此只要知道某个前缀在 ``1..n`` 中包含多少个整数,就能整棵跳过它。
对前缀 ``prefix``,维护当前层的首值 ``first`` 和开区间右端 ``last``。每向下一层就把两者都乘以 10,并把本层与 ``n`` 的交集加入计数。主循环从 ``1`` 开始,``k`` 改成从 0 开始的剩余排名:若当前前缀的数量不超过排名,就移动到下一个兄弟;否则进入当前前缀的下一层,并消耗掉前缀节点本身的一个排名。
C++ 实现
--------
.. code-block:: cpp
class Solution {
long long countPrefix(long long prefix, long long n) {
long long first = prefix;
long long last = prefix + 1; // [first, last)
long long count = 0;
while (first <= n) {
count += std::min(n + 1, last) - first;
first *= 10;
last *= 10;
}
return count;
}
public:
int findKthNumber(int n, int k) {
long long prefix = 1;
long long rank = static_cast(k) - 1;
while (rank > 0) {
long long count = countPrefix(prefix, n);
if (count <= rank) {
++prefix;
rank -= count;
} else {
prefix *= 10;
--rank;
}
}
return static_cast(prefix);
}
};
代码分析
--------
``countPrefix`` 统计的是一个字典树前缀的完整子树大小,而不是数值区间的长度,所以能正确处理 ``19`` 后面紧接着 ``2`` 的字典序规则。跳过兄弟分支时排名减少整棵子树的数量,向下时只减少当前前缀节点;循环始终保留第 ``k`` 个数所在的分支。每次处理一个十进制层级,时间复杂度为 ``O(log n)``,额外空间复杂度为 ``O(1)``。