题目
给定整数 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
解题
- 确定指定前缀下所有子节点数
getCount - 第k个数在不在当前前缀下
2.1不在当前前缀下
2.1在当前前缀下
方法一：字典树思想
思路：（例：比如要查找第5个数,n=199）
1.找到当前前缀的下的数目 (例： 前缀为1 ,是第一个数 )
2.如果是在当前前缀下的，那么就缩小搜索范围(例:10，是第二个数)，否则就换下一个前缀（例：2）
3. (例：100，是第三个数）
4. (例： 以100为前缀，没有这个数，因此cnt+=temp,得到102)
class Solution { public: int findKthNumber(int n, int k) { int cnt=0; // 已经经过的元素个数, 开始一个元素都没有经过, 所以个数为 0 int num=1; // 第一个元素 (经过 i 个元素, 当前 num 是第 i + 1 元素) while (true) { if (cnt == k - 1) { // 经过了 k - 1 个元素找到了第 k 个元素 break; } int temp = getCount((long) num, n); // 以 num 为根, 以 n 为最大值的十叉树的元素总个数 if (cnt + temp >= k) { // 以 num 为根的十叉树内有第 k 个元素 num *= 10; cnt++; } else if (cnt + temp < k) { // 以 num 为根的十叉树内没有第 k 个元素 num++; cnt += temp; } } return num; } int getCount(long num,int n){ int cnt=0;// 元素总个数 int width=1; // 当前层数的宽度, 第一层只有 num 一个元素, 所以第一层宽度为 1 while(true){ if(num+width-1<=n){ // n 的值大于等于当前层的最大值, 说明当前层数的个数可以全部添加 cnt+=width; num*=10; width*=10; } else{// n 的值小于当前层的最大值则只能添加部分个数或者不添加, 并跳出循环 if(n-num>=0){ cnt+=n-num+1; } break; } } return cnt; } };
