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

首先摆上题目:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

摘自leetcode，本人最近刚买vip，因此看得到企业的出题频率：）文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

乍一看这一题貌似毫无头绪，什么是字典序？如何定位这个数？没错，刚接触这个题目的时候，我的脑筋里也是一团乱麻。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

但是我觉得作为一个拥有聪明才智的程序员来说，最重要的能力就是迅速抽象问题、拆解问题的能力。经过一段时间的思考，我的脑筋里还是没有答案。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

哈哈。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

言归正传，我们来分析一下这个问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

首先，什么是字典序？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

什么是字典序？

简而言之，就是根据数字的前缀进行排序，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

比如10 < 9，因为10的前缀是1，比9小，文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

再比如112 < 12，因为112的前缀11小于12。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

这样排序下来，会跟平常的升序排序会有非常大的不同。先给你一个直观的感受，一个数乘10，或者加1，哪个大？可能你会吃惊，后者会更大。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

但其实掌握它的本质之后，你一点都不会吃惊。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

问题建模

画一个图你就懂了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

每一个节点都拥有10个孩子节点，因为作为一个前缀 ，它后面可以接0~9这十个数字。而且你可以非常容易地发现，整个字典序排列也就是对十叉树进行先序遍历。1, 10, 100, 101, ... 11, 110 ...文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

回到题目的意思，我们需要找到排在第k位的数。找到他的排位，需要搞清楚三件事情:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

1. 怎么确定一个前缀下所有子节点的个数？
2. 如果第k个数在当前的前缀下，怎么继续往下面的子节点找？
3. 如果第k个数不在当前的前缀，即当前的前缀比较小，如何扩大前缀，增大寻找的范围？

接下来 ，我们一一拆解这些问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

理顺思路

1. 确定指定前缀下所有子节点数

现在的任务就是给定一个前缀，返回下面子节点总数。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

我们现在的思路就是用下一个前缀的起点减去当前前缀的起点，那么就是当前前缀下的所有子节点数总和啦。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

//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还是有些问题的，我们来修正这个问题:文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

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

你可能会问:咦？怎么是n+1,而不是n呢？不是说好了n是上界吗？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

我举个例子，假若现在上界n为12，算出以1为前缀的子节点数，首先1本身是一个节点，接下来要算下面10，11，12，一共有4个子节点。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

那么如果用Math.min(n, next) - cur会怎么样？文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

这时候算出来会少一个，12 - 10加上根节点，最后只有3个。因此我们务必要写n+1。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

现在，我们搞定了前缀的子节点数问题。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

2. 第k个数在当前前缀下

现在无非就是往子树里面去看。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

prefix这样处理就可以了。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

prefix *= 10
复制代码

3.第k个数不在当前前缀下

说白了，当前的前缀小了嘛，我们扩大前缀。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

prefix ++;
复制代码

框架搭建

整合一下刚刚的思路。文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html

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;
};
复制代码

成功AC！文章源自菜鸟学院-https://www.cainiaoxueyuan.com/suanfa/16706.html