LeetCode 440

分桶尝试

看到这道题之后，手算了一下。发现一个规律，在按照字典序对所有的整数排序之后，最高位为1的数字全部排在最高位为2的前面，最高位为2的排在最高位为3的前面……

假设最高位为1的数字有10个，但是我们要返回第12个数字，那么就可以完全跳过所有最高位为1的数字，在剩下的数字中，查找第12 - 10 = 2个数字。在查找剩下的数字时，又可以递归进行上面的步骤。

发现这个规律之后，尝试用分桶的方案解决这个问题。将数字由高位到低位进行递归分桶，然后根据桶的大小和要返回数字的序号，跳过一些桶。

分桶时，如果某些数字位数不够，就将这个数字分到0号桶上；比如数字23，当我用从高往低按照第三位分桶时，第三位不存在，就将23放到0号桶中。

def bucket_sort(self, items, p):
    results = [[] for _ in range(10)]
    for item in items:
        if len(item) > p:
            i = ord(item[p]) - ord('0')
            results[i].append(item)
        else:
            results[0].append(item)
    return results

按照这个思路，在跑测试用例的时候，发现一个badcase。数字1、10、100是分到一个桶中的，而且在接下来的递归分桶步骤中，无法将这三个数字分开。这是分桶算法的局限造成的，在运行分桶算法时，必须保证每个元素的位数相同。

所以这个方案失败了。即使这个方案能够成功，也只能减少排序的次数，内存开销是减少不了的。

原始尝试

查找解法的时候，看到了一个非常简单的方案。因为字典序是按照字符串的规则来排序的。所以可以将所有的整数转成字符串，再排序，返回第k个元素。

class Solution:
   def findKthNumber(self, n: int, k: int) -> int:
       return sorted(map(str, [i for i in range(1, n + 1)]))[k - 1]

Denary Tree尝试

在分桶的尝试中，思路是通过递归的方法，选择上一轮分桶结果的某个桶进行这一轮分桶。递归调用实际上会形成一棵递归调用的树。

这个博主说明了如何用这棵递归调用树求解。

求解过程形成的递归调用树是一个Denary Tree。树的第1层存储位数为1的树，第2层存储位数为2的树，数字按照前缀形成父子节点关系；比如10、11、12是1的子节点，234、235是23的子节点。

这种树的第一个特点是，先序遍历的结果就是树中所有数字的字典序排列。所以按照先序遍历返回的第k个结果就是解。

在遍历的时候，如果发现子树节点的数量少于k，那么就可以跳过它，降低时间复杂度。

如何确定一棵子树有多少节点呢？以节点为1的子树举例。一个子树的节点数量，等于每一层节点的数量之和。第一层就1个节点1，第二层是10～19有20个节点，第三层是100～199有100个节点。第一层开头的节点是1，第二层是10，第三层是100，按照层数节点的值是10倍的关系；每一层最后一个节点的值，是下一个子树中，相同层数的第一个节点的值减1。

再考虑算子树节点数量的边界情况。在按层求子树节点数量时候，如何知道这棵子树有多少层，需要算到哪一层呢？可以按照n值做限制，每一层的第一个节点的值一定小于等于n，不然这一层就不存在。之前算子树每一层节点数量的时候，每一层的节点是满的，但是到了最后一层，节点数量可能不满。可以比较这一层在满节点情况下最后一个节点的值和n的大小，如果n较小，就说明这一层节点不满，节点的值最多到n。

按照这个思路得到的代码如下。

class SolutionFast:
   def findKthNumber(self, n: int, k: int) -> int:
       curr = 1
       k -= 1
 
       while k:
           first = curr
           last = curr + 1
           step = 0
 
           while first <= n:
               step = step + min(last, n + 1) - first
              
               first = first * 10
               last = last * 10
 
           if step <= k:
               k -= step
               curr += 1
           else:
               k -= 1
               curr *= 10
 
       return curr