题目

题目来源：力扣（LeetCode）

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 109。

示例 :

输入:
n: 13 k: 2

输出:
10

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

思路分析

什么是字典序？
简而言之，就是根据数字的前缀进行排序，

比如 10 < 9，因为 10 的前缀是 1，比 9 小。

再比如 112 < 12，因为 112 的前缀 11 小于 12。

数字序列的字典序有一个特点：

以数字 i 开头的所有数字串 按字典序一定 排在以数字 i+1 开头的所有数字串的前面。

对每个数字 i，唯一能做的就是确定以数字 i 开头的字符串的个数。

但是有一个限制是，以 i 开头的数字不能超过最大数字 nn。

比如 i=1 时，以 1 开头的有 1,10,11,12,13,14,15,16,17,18,19。

如 n=12，则数字只能是 1，10，11。以 1 开头的数字串共有 3 个。

算法思路

  1. 确定指定前缀下所有子节点数，给定一个前缀，返回下面子节点总数。就是用下一个前缀的起点减 去当前前缀的起点，那么就是当前前缀下的所有子节点数总和。
  2. 第k个数在当前前缀下，往子树里面去看。prefix *= 10
  3. 第k个数不在当前前缀下，当前的前缀小了，我们扩大前缀。
  1. /**
  2.  * @param {number} n
  3.  * @param {number} k
  4.  * @return {number}
  5.  */
  6. var findKthNumber = function (n, k) {
  7.   // prefix 是前缀，n 是上届
  8.   let getCount = (prefix, n) => {
  9.     let count = 0;
  10.     // next 是下一个前缀
  11.     // cur <= n 当前前缀不能大于上届
  12.     for (let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10)
  13.       count += Math.min(next, n + 1) - cur; // 下一个前缀的起点减去当前前缀的起点
  14.     return count;
  15.   }
  16.   let p = 1;//作为一个指针，指向当前所在位置，当p==k时，也就是到了排位第k的数
  17.   let prefix = 1;//前缀
  18.   while (p < k) {
  19.     let count = getCount(prefix, n);//获得当前前缀下所有子节点的和
  20.     if (p + count > k) {//第k个数在当前前缀下
  21.       prefix *= 10;
  22.       p++;//把指针指向了第一个子节点的位置，比如11乘10后变成110，指针从11指向了110
  23.     } else if (p + count <= k) {//第k个数不在当前前缀下
  24.       prefix++;
  25.       p += count;//注意这里的操作，把指针指向了下一前缀的起点
  26.     }
  27.   }
  28.   return prefix;
  29. };