Leetcode 440

Link:

440. 字典序的第K小数字 - 给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。示例 1: 输入: n = 13, k = 2 输出: 10 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。示例 2: 输入: n = 1, k = 1 输出: 1 提示: * 1 <= k <= n <= 109

https://leetcode.cn/problems/k-th-smallest-in-lexicographical-order/description

题目要求

给定整数n和k，根据字符串顺序排列（e.g. 1, 10, 11, … , 2, 20…) 1到n的所有整数，求第k小的数

核心算法和原理

朴素排序肯定太慢

如果将这些数构建成一颗由1 ~ 9组成的Trie树（左到右1~9），则中序遍历的结果就是这个序列

两个相邻数(a and a + 1)之间的排序位置的差即为以左边节点为根节点的子树的节点个数，且这是computable的，从这个特性下手

计算方法

一层一层的计算左边这颗子树的节点个数，每一层节点数为

解释：这一层如果满那么就是从a * 10 ^ layer 到 (a + 1) * 10 ^ layer - 1 (e.g. 1000 → 1999)，不满（e.g. n = 1524不会出现1 → 5 → 2 → 5）则为 (n+1) - a * 10 ^ layer ( 1000 → 1524 )
层层叠加到a * 10 ^ layer恰好小于等于n即可

算法过程

从a = 1开始，用i记录a现在是第几小的数

当i < k时，计算a 和 a+1之间的节点差gap

若i + gap ≤ k，说明第k大的数的节点一定在以大于等于a + 1 为根节点的子树里，将a设为右边的节点( a++ )，重复2

若非，则说明就在以a为根节点的子树里，将a设为最左的直接子节点( a *= 10 )，重复2

此时得到的a就是第k小的数

复杂度分析

时间复杂度O (8 · lgN · lgN)（算gap次数 + 遍历层数 + 横向移动次数）

代码


class Solution {
public:
    int findKthNumber(int n, int k) {
        int i = 1, gap = 0;
        int a = 1;
        while (i < k) {
            gap = getGap(a, a + 1, n);
            if (i + gap <= k) {
                a++;
                i += gap;
            } else {
                a *= 10;
                i++;
            }
        }
        return a;
    }

    int getGap(long a, long b, long n) {
        int gap = 0;
        while (a <= n) {
            gap += min(b, n + 1) - a;
            a *= 10;
            b *= 10;
        }
        return gap;
    }
};