lc440. 字典序的第K小数字（计数模拟）

给定整数 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

class Solution {
    public int findKthNumber(int n, int k) {
        int ans = 1;
        while (k > 1) {
            int cnt = getCnt(ans, n);
            //当这个前缀数字的数量小于k时，说明不在这个范围内，减去cnt，增加前缀
            if (cnt < k) {
                k -= cnt; ans++;
            } else {    //在这个范围内，减去当前这个数，ans * 10
                k--; ans *= 10;
            }
        }
        return ans;
    }
    //返回满足某个前缀到limit的数量
    int getCnt(int x, int limit) {
        //limit = 12345, x = 123, u = 124 u是limit前n个前缀
        String a = String.valueOf(x), b = String.valueOf(limit);
        int n = a.length(), m = b.length(), k = m - n;
        int ans = 0, u = Integer.parseInt(b.substring(0, n));
        //x0-x9 x00-x99
        for (int i = 0; i < k; i++) ans += Math.pow(10, i);
        if (u > x) ans += Math.pow(10, k);//都满足要求
        else if (u == x) ans += limit - x * Math.pow(10, k) + 1;//后面的满足要求
        return ans;
    }
}