算法实例教学：字典序的第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解决方案方法一字典树思想思路题目要求找到字典序第 k 小的数字可以将所有的数字都转换成字符串然后排序找到第 k 小的数字即可但显然时间复杂度不符合要求。我们利用字典树的特性将所有小于等于 n 的数字按照字典序的方式进行重建可以得到如下