440. K-th Smallest in Lexicographical Order

source: https://leetcode.com/problems/k-th-smallest-in-lexicographical-order/

Question

Given two integers n and k, return the kth lexicographically smallest integer in the range [1, n].

暴力法

这道题比较自然的反应是生成数组，然后排序，再通过数组索引选择。

var findKthNumber = function(n, k) {
    return Array(n).fill(0).map((_, i) => `${i + 1}`).sort()[k - 1];
};

这样子的时间复杂度在O(nlogn), 空间复杂度在O(logn). 这道题n的数字会很大，会导致oom.

字典树

这题的核心在于，字典树就是一个十叉树的结构，而对于一个树形的结构，因为已知总节点数，他的某个子节点数是可计算的。

通过这个原理：

• 如果此节点下的子节点数小于k，说明k在子节点内，继续以第一个子节点为节点计算
• 如果此节点下的子节点数大于k，说明k不在子节点内，继续以下一个兄弟节点为节点计算

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function (n, k) {
  const getCount = prefix => {
    let cur = prefix;
    let next = prefix + 1; //下一个前缀
    let count = 0;
    //当前的前缀当然不能大于上界
    while (cur <= n) {
      count += Math.min(n + 1, next) - cur; //下一个前缀的起点减去当前前缀的起点
      cur *= 10;
      next *= 10;
      // 如果说刚刚prefix是1，next是2，那么现在分别变成10和20
      // 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层

      // 如果说现在prefix是10，next是20，那么现在分别变成100和200，
      // 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层
    }
    return count; //把当前前缀下的子节点和返回去。
  };

  let p = 1; //作为一个指针，指向当前所在位置，当p==k时，也就是到了排位第k的数
  let prefix = 1; //前缀
  while (p < k) {
    let count = getCount(prefix); //获得当前前缀下所有子节点的和
    if (p + count > k) {
      //第k个数在当前前缀下
      prefix *= 10;
      p++; //把指针指向了第一个子节点的位置，比如11乘10后变成110，指针从11指向了110
    } else if (p + count <= k) {
      //第k个数不在当前前缀下
      prefix++;
      p += count; //注意这里的操作，把指针指向了下一前缀的起点
    }
  }
  return prefix;
};

总结

这道题是以字典树为基础去做计算，注意一些细节，平时多熟悉类似题目。