440.字典序的第K小数字

链接：440.字典序的第K小数字
难度：Hard
标签：字典树
简介：给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

题解 1 - typescript

• 编辑时间：2021-10-26
• 执行用时：76ms
• 内存消耗：39.4MB
• 编程语言：typescript
• 解法介绍：构建字典树，计算每个字数包含的节点数。

function findKthNumber(n: number, k: number): number {
  for (let i = 1; i <= 9; i++) {
    const c = count(i);
    if (c < k) k -= c;
    else return find(i, k);
  }
  return 0;
  function find(prifix: number, k: number): number {
    if (k === 1) return prifix;
    k--;
    for (let i = 0; i <= 9; i++) {
      const next = prifix * 10 + i;
      if (next > n) continue;
      const c = count(next);
      if (c >= k) return find(next, k);
      else k -= c;
    }
    return 0;
  }
  function count(prifix: number): number {
    let nextPrifix = prifix + 1;
    let ans = 0;
    while (prifix <= n) {
      ans += Math.min(n + 1, nextPrifix) - prifix;
      prifix *= 10;
      nextPrifix *= 10;
    }
    return ans;
  }
}