LeetCode440：字典序的第K小数字

题目

给定整数 n 和 k，找到 1 到 n 中字典序第 k 小的数字。

注意：1 ≤ k ≤ n ≤ 10^9。

Solution

我们可以把每个字符看作是字符串，这样我们只需要考虑前缀即可。显然最小的字符串一定是0，然后是所有以1开头的数。。。

我们只需要枚举所有首位数字 $1-9$，计算每个前缀在区间 $[0, n]$ 内有多少个数就好了，当累加和超过 $n$ 时，说明答案一定是以这个首位数字开头的，然后向下枚举。比如当以得知答案以3开头时，扣除3本身，然后向下枚举前缀30,31重复上述操作。。。直到 $k$ 为0。

Code

class Solution {
    public int get_Count(int n, long x, long y) {
        int sum = 0;
        while (x <= n) {
            sum += Math.min(n + 1, y) - x;  // 如n=15,则sum+=min(16,20)-10
            x *= 10;
            y *= 10;
        }
        return sum;
    }
    public int findKthNumber(int n, int k) {
        int pre = 1;
        k--; // 扣除数字0
        while (k > 0) {
            int now = get_Count(n, pre, pre + 1);
            if (k >= now) {  // 说明不在这个前缀区间里
                pre++;  // 找下一个字典序前缀
                k -= now;  // 扣除这个前缀的所有数
            } else {  // 说明答案是这个前缀
                pre *= 10;  // 往下找
                k--; // 扣除当前这个数
            }
        }
        return pre;
    }
}