【LeetCode】440. 字典序的第K小数字

发表于 更新于 分类于 Valine：
本文字数： 244 阅读时长 ≈ 1 分钟

440. 字典序的第K小数字

思路

  1. 画出字典树
    字典树
  2. k表示要找到后面的第k个元素，起始下标是0
  3. 获取以prefix开头的数字个数，包括他本身
    • 如果数字个数大于k，下移，在prefix*10下的子树进行查找
    • 如果数字个数小于等于k，右移，在prefix+1下的子树进行查找

问题的关键是求解 以prefix开头的数字个数，包括他本身

  • 根节点 [prefix, prefix+1 )
  • 第一层 [prefix*10, (prefix+1)*10 )
  • 第二层 [prefix*100, min(n+1, (prefix+1)*100) )
  • …

代码

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
26
27
class Solution {
public:
typedef long long LL;
    int findKthNumber(int n, int k) {
        int prefix = 1;
        //扣除掉第一个0节点
        k--; // k记录要找的数字在prefix后的第几个
        while (k>0){
            int cnt = getCnt(n, prefix); // 当前prefix 下有多少个元素;包含prefix
            if (cnt <= k) { // 向右 第k个数不在以prefix为根节点的树上
                k -= cnt;
                prefix++;
            } else { // 向下 在子树中
                k--; //刨除根节点
                prefix*=10;
            }
        }
        return prefix;
    }
    int getCnt(LL n, LL prefix){
        LL cnt = 0;
        for (LL first = prefix, second = prefix+1; first<=n; first*=10, second*=10){
            cnt+= min(n + 1, second) - first;
        }
        return cnt;
    }
};