How does a Trie help solve the K-th Smallest in Lexicographical Order problem?

A Trie allows us to simulate the lexicographical order of numbers and efficiently count how many numbers are smaller than a given candidate, enabling us to find the k-th smallest number without generating all numbers explicitly.

What is the time complexity of the Trie-based approach?

The time complexity is O(log(n)^2), as it involves traversing a Trie-like structure and counting numbers with each prefix.

Why can't we generate all numbers from 1 to n to solve this problem?

Generating all numbers from 1 to n would be too slow, especially when n is very large. Instead, the Trie-based approach allows us to find the k-th smallest number more efficiently.

What is the key idea behind the Trie-based strategy for this problem?

The key idea is to navigate through a Trie-like structure, counting how many numbers are smaller than the current prefix, and adjusting the search to find the k-th smallest number without generating all the numbers.

How can I handle edge cases for small values of k and n?

Edge cases can be handled by ensuring that the counting function correctly accounts for the smallest and largest possible values of k and n, and adjusting the candidate number appropriately.

#440

Hard

auto_awesome字典树·driven·solution·strategy

LeetCode 题解工作台

字典序的第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 =…

字典树

题目描述

给定整数 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 <= 10⁹

lightbulb

解题思路

方法一：字典树计数 + 贪心构造

本题要求在区间 $[1, n]$ 中，按字典序排序后，找到第 $k$ 小的数字。由于 $n$ 的范围非常大（最多可达 $10^9$ ），我们无法直接枚举所有数字后排序。因此我们采用贪心 + 字典树模拟的策略。

我们将 $[1, n]$ 看作一棵 十叉字典树（Trie）：

每个节点是一个前缀，根节点为空串；
节点的子节点是当前前缀拼接上 $0 \sim 9$ ；
例如前缀 $1$ 会有子节点 $10, 11, \ldots, 19$ ，而 $10$ 会有 $100, 101, \ldots, 109$ ；
这种结构天然符合字典序遍历。

根
├── 1
│   ├── 10
│   ├── 11
│   ├── ...
├── 2
├── ...

我们使用变量 $\textit{curr}$ 表示当前前缀，初始为 $1$ 。每次我们尝试向下扩展前缀，直到找到第 $k$ 小的数字。

每次我们计算当前前缀下有多少个合法数字（即以 $\textit{curr}$ 为前缀、且不超过 $n$ 的整数个数），记作 $\textit{count}(\text{curr})$ ：

如果 $k \ge \text{count}(\text{curr})$ ：说明目标不在这棵子树中，跳过整棵子树，前缀右移： $\textit{curr} \leftarrow \text{curr} + 1$ ，并更新 $k \leftarrow k - \text{count}(\text{curr})$ ；
否则：说明目标在当前前缀的子树中，进入下一层： $\textit{curr} \leftarrow \text{curr} \times 10$ ，并消耗一个前缀： $k \leftarrow k - 1$ 。

每一层我们将当前区间扩大 $10$ 倍，向下延伸到更长的前缀，直到超出 $n$ 。

时间复杂度 $O(\log^2 n)$ ，空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

class Solution:
    def findKthNumber(self, n: int, k: int) -> int:
        def count(curr):
            next, cnt = curr + 1, 0
            while curr <= n:
                cnt += min(n - curr + 1, next - curr)
                next, curr = next * 10, curr * 10
            return cnt

        curr = 1
        k -= 1
        while k:
            cnt = count(curr)
            if k >= cnt:
                k -= cnt
                curr += 1
            else:
                k -= 1
                curr *= 10
        return curr

speed

复杂度分析

指标	值
时间	O(\log(n)^2)
空间	O(1)

psychology

面试官常问的追问

外企场景

question_mark
Can the candidate describe a method that avoids iterating through all numbers from 1 to n?
question_mark
Did the candidate implement an efficient counting function that works without generating all possible numbers?
question_mark
Does the candidate understand how a Trie-driven approach can optimize the search for the k-th smallest number?

warning

常见陷阱

外企场景

error
Not implementing the Trie structure efficiently, leading to excessive time complexity.
error
Misunderstanding the counting mechanism and generating all numbers explicitly instead of using the prefix-based counting approach.
error
Failing to consider edge cases, such as when k is at the upper or lower bound of the range.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Solving the problem with a simple iterative approach (not optimized).
arrow_right_alt
Optimizing the approach further to handle extremely large values of n and k by leveraging more advanced Trie techniques.
arrow_right_alt
Adapting the algorithm to handle different ranges or non-integer inputs in a lexicographical order.

help

常见问题

外企场景

继续练习

#421 数组中两个数的最大异或值 #472 连接词 #386 字典序排数