字典序第 k 小数字

字典序与前序遍历是什么关系？

• 字典序: 数字按字符串形式比较大小得到的顺序;
• 等价结构: 把 1 ~ n 建成字典树后, 字典序就是这棵树的前序遍历;
• 前序遍历: 先访问当前节点, 再依次访问各子节点;
• 直接遍历的问题: 需要枚举全部节点, n 很大时超时;

如何用计数跳过整棵子树？

• 核心: 用数学方法求出以 cur 为根的子树中不超过 n 的节点个数;
• 逐层计数: 每层累加 min(next, n + 1) - cur, 然后 cur *= 10、next *= 10 进入下一层;
• 下降: 若剩余 k 落在该子树内, step++ 并移动到 cur * 10;
• 跳过: 否则把子树节点数从 k 中减去, 并移动到 cur + 1;

function findKthNumber(n: number, k: number): number {
  const getStep = (cur: number, next: number): number => {
    let step = 0;
    while (cur <= n) {
      step += Math.min(next, n + 1) - cur;
      cur *= 10;
      next *= 10;
    }
    return step;
  };

  let step = 1;
  let result = 1;
  while (step < k) {
    const count = getStep(result, result + 1); // 以 result 为根的子树节点数
    if (step + count > k) {
      step++;
      result *= 10; // 答案在子树内, 继续下降
    } else {
      step += count;
      result++; // 跳过整棵子树
    }
  }

  return result;
}

计数过程的复杂度是多少？

• 计数: 每层 O(1), 共 O(log n) 层, 单次计数 O(log n);
• 主循环: 每次下降或跳过都至少消耗一个节点名额, 最多推进 O(k) 次;
• 空间: O(1);