虚拟交叉树建模问题，面试率最高的算法之一

先问个问题：

取自leetcode，最近买了VIP所以可以看到公司问问题的频率：）

乍一看，这个问题似乎毫无头绪。字典中的顺序是什么？如何找到这个号码？是的，当我第一次看到这个话题时，我的脑子一片混乱。

但我认为，作为一个聪明的程序员，最重要的能力就是快速抽象和揭露问题的能力。想了一会儿，我心里还是没有答案。

哈哈。

言归正传，我们来分析一下这个问题。

首先什么是字典顺序？

字典中的顺序是什么？

简而言之，这是按数字前缀排序，

例如 10 例如 112 这种排序方式与通常的升序有很大不同。先给大家直观感受一下。一个数乘以 10 和加 1 哪个更大？您可能会惊讶地发现后者更大。

但其实，当你掌握了它的本质时，你就不会感到惊讶了。

问题建模

画个图你就明白了。

每个节点有10个子节点，因为它后面可以跟0到9的十个数字作为前缀，可以很容易看出整个字典顺序是顺序之前的跨树遍历。 1, 10, 100, 101, ... 11, 110 ...

回到题意，我们需要找到第k个数。要找到它的排名，你需要弄清楚三件事：

1. 如何确定一个前缀下的所有子节点的数量？
2. 如果第k个数字低于当前前缀，如何继续寻找下一个子节点？
3. 如果第k个数字不在当前前缀中，说明当前前缀比较小，如何扩大前缀，增大搜索范围呢？

来吧，让我们一一解决这些问题。

理清思路

1。确定给定前缀下的所有子节点的数量

当前的任务是给出前缀并返回下面的子节点总数。

我们现在的想法是，用下一个前缀的起点减去当前前缀的起点，那么这就是当前前缀下所有子节点的总数。

//prefix是前缀，n是上界
var getCount = (prefix, n) => {
    let cur = prefix;
    let next = prefix + 1;//下一个前缀
    let count = 0;
    //当前的前缀当然不能大于上界
    while(cur <= n) {
        count += next - cur;//下一个前缀的起点减去当前前缀的起点
        cur *= 10; 
        next *= 10;
        // 如果说刚刚prefix是1，next是2，那么现在分别变成10和20
        // 1为前缀的子节点增加10个，十叉树增加一层, 变成了两层
        
        // 如果说现在prefix是10，next是20，那么现在分别变成100和200，
        // 1为前缀的子节点增加100个，十叉树又增加了一层，变成了三层
    }
    return count;//把当前前缀下的子节点和返回去。
}
复制代码

当然，我不知道你是否发现了问题。当next的值大于上界时，以该前缀为根节点的生成树不是全生成树。它应该达到上限，然后不再有子节点。所以count += next - cur 仍然存在一些问题。让我们解决这个问题：

count += Math.min(n+1, next) - cur;
复制代码

你可能会问：什么？为什么是n+1而不是n？我们不是同意 n 是上限吗？

让我举个例子。如果n的上限为12，则统计以1为前缀的子节点的数量。首先，1是唯一的节点，然后统计接下来的10、11、12，总共有4个子节点。

那么如果您使用 Math.min(n, next) - cur 会发生什么？

这时候算出来就少了一个，12 - 10加上根节点最后就只剩下3了，所以要写n+1。

我们现在已经解决了子前缀节点数量的问题。

2。第 k 个数字位于当前前缀

下，现在除了在子树中查找之外无事可做。前缀

可以这样处理。

prefix *= 10
复制代码

3。这个K数不在当前前缀

之下，坦白说，现在的前缀太小了，那我们就扩大一下前缀吧。

prefix ++;
复制代码

构建框架

立即连接想法。

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

查看完整代码

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findKthNumber = function(n, k) {
  let getCount = (prefix, n) => {
    let count =  0;
    for(let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) 
      count += Math.min(next, n+1) - cur;
    return count;
  }
  let p = 1;
  let prefix = 1;
  while(p < k) {
    let count = getCount(prefix, n);
    if(p + count > k) {
      prefix *= 10;
      p++;
    } else if(p + count <= k) {
      prefix ++;
      p += count;
    }
  }
  return prefix;
};
复制代码

无障碍交流！

作者：沉三元
链接：https://juejin.im/post/5d7fb1e16fb9a06ac76de435
来源：掘金
版权归作者所有。商业转载请联系作者获得许可。非商业转载请注明来源。