[LeetCode]K-th Smallest in Lexicographical Order

乍看之下很像寻找array中第k大的数，这样我们用quick select的方法可以达到O(n)的时间复杂度。但是这道题显然还有更效率的办法，参考这篇文章我们可以发现这就是一个denary tree，寻找第字典序第k大的数，就是preorder traversal的第k个节点，但是显然我们不需要O(k)的时间，我们在每一层算出答案应该在哪个节点的子树当中，我们去子树继续寻找。比如对于[1, 233]的区间，我们寻找字典序第123大的数：

• 我们首先算以1为根的子树的大小，其大小为111（1, 10->19, 100->199），说明我们可以直接跳过1
• 继续计算2位根的子树大小，大小为45（2，20->29，200->233），说明答案在以2位根子树当中，我们去子树中继续搜寻第123 - 111 = 12大的数
• 同理我们跳过10位根的子树，因为其size为11（10，100-109）
• 我们到了12后发现要找第一大的数，那么也就是12，return 结果

时间复杂度O(d)，d为10十进制下的位数，所以我们也可以表示成O(log10(n)) = O(log n)，代码如下：