来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order
题目描述
给定整数 n 和 k，返回 [1, n] 中字典序第 k 小的数字。 示例 1: 输入: n = 13, k = 2 输出: 10 解释: 字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。 示例 2: 输入: n = 1, k = 1 输出: 1 提示: 1 <= k <= n <= 109
解题思路
根据题意，最简单的方法是造一棵字典树，将1-n的数字全部存入，并且前序遍历所有数字，第k个就是答案，但是观察数据大小，应该会超时，果然就超时了。
通过观察，发现造出的字典树是一颗完全树，所以可以利用这个规律来虚拟字典上，并不需要真正造一颗树。对于结点i来说，i拥有的子树中结点个数为icount, 如果icount < k，那么寻找的结点不在这个子树中，寻找下一个相邻的结点，否则，寻找的结点就在这颗子树中，向下寻找i结点的每个子树。
由于字典树是满二叉树，所以求取i的结点数可以用虚拟的层次遍历，假设第j层左结点是x1，最右结点是x2，那么这一层的结点个数就是x2 - x1 + 1，下一层左结点x3 = x1 * 10， 右结点x4 = x2 * 10 + 9 或者 n。
代码展示
字典树 + dfs：
class Solution { public: struct TreeNode { int val; TreeNode* ch[10]; TreeNode(int val) { this->val = val; for (int i = 0; i < 10; i++) { this->ch[i] = NULL; } } }; int miRet = 0; void dfs(TreeNode *root, int &k) { if (!root) return; k--; if (k < 0) return; if (k == 0) { miRet = root->val; return; } for (int i = 0; i < 10; i++) dfs(root->ch[i], k); } int findKthNumber(int n, int k) { TreeNode* root = new TreeNode(0); for (int i = 1; i <= n; i++) { TreeNode* p = root; string str = to_string(i); for (int j = 0; j < str.size(); j++) { if (p->ch[str[j] - '0'] == NULL) { p->ch[str[j] - '0'] = new TreeNode(0); } p = p->ch[str[j] - '0']; } p->val = i; } int iTemp = k + 1; dfs(root, iTemp); return miRet; } };
虚拟字典树+ 虚拟遍历：
class Solution { public: int MyCount(int i, long n) { int iCount = 0; long iFirst = i; long iLast = i; while(iFirst <= n) { iCount += min(iLast, n) - iFirst + 1; iFirst *= 10; iLast = iLast * 10 + 9; } return iCount; } int findKthNumber(int n, int k) { int iCur = 1; k--; while(k > 0) { int iCount = MyCount(iCur, n); if(iCount <= k) { k -= iCount; iCur++; } else { iCur *= 10; k--; } } return iCur; } };
运行结果
