LeetCode 440 K-th Smallest in Lexicographical Order

Posted on | In | 阅读

按字典序排列1~n的数字字符串，找到第k个是什么数字

  1. 把所有的数字看作是在一个字典树上，每个结点最多有10个子节点
  2. 一个个结点搜索，可以预先计算出这个结点所有子节点的数目，并加起来与k作比较，还不够则搜索下一个兄弟结点，否则就遍历到子节点继续计算子节点数量。
  3. prefix记录的是当前从根节点到当前结点的路径，prefix+1则是下一个兄弟结点的路径。
  4. 以样例输入为例。例如计算1的子节点数，那么先计算1~2之间的个数（1个），然后计算10~20之间的个数（4个）。。。
  5. 若prefix的子节点数量超过了还需要的数量，那么搜索prefix的第一个子节点，即prefix*10 与 prefix*10 + 1

C++ Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    int findKthNumber(int n, int k) {
        long long prefix = 1;
        k--;
        while(k > 0){
            long long from = prefix;
            long long to = prefix + 1;
            long long step = 0;
            while(from <= n){
                step += min((long long)n+1, to) - from;
                from *= 10;
                to *= 10;
            }
            if(step <= k){
                k -= step;
                prefix++;
            }else{
                prefix *= 10;
                k--;
            }
        }
        return prefix;
    }
};