18、字典序的第K小数字

题目：

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

注意：1 ≤ k ≤ n ≤ 109。

示例 :

输入:
n: 13 k: 2
输出:
10

解释:

字典序的排列是 [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9]，所以第二小的数字是 10。

解答：

var findKthNumber = function(n, k) {
    let getCount = (prefix, n) => {
        let cnt = 0;
        for (let cur = prefix, next = prefix + 1; cur <= n; cur *= 10, next *= 10) {
            cnt += Math.min(next, n + 1) - cur; 
            // n = 13时，cnt = min(2, 14) - 1 + min(20, 14) - 10 = 5;
        }
        return cnt;
    }
    let p = 1;
    let prefix = 1;
    while (p < k) {
        let cnt = getCount(prefix, n); // 以prefix开头的数字数量
        if (p + cnt > k) {
            prefix *= 10; // 缩小范围
            p++; // p 往后移一位
        } else if (p + cnt <= k) {
            prefix++; // prefix + 1
            p += cnt; // p 跨越 cnt
        }
    }
      console.log(prefix);
    //return prefix;
};
n = 13;   k = 2;
findKthNumber(n, k);

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/k-th-smallest-in-lexicographical-order
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。