440-字典序的第K小数字

LeetCode 440. 字典序的第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。

method

可以模拟构建一棵前缀树，当前节点i，下一层的最左边节点为i*10，最右边节点为i*10+9，这样就可以计算出这一层的节点数为last-first+1，last可能到不了这么多，需要min(last, n)

• 如果step小于等于k，说明第k小的节点在i节点的下一个节点上
• 如果step大于k，说明第k小的节点在i的子节点中

int getNode(int cur, long n) {
    long first = cur, last = cur;
    int step = 0;
    while (first <= n) {
        step += min(n, last) - first + 1;
        first = first * 10;
        last = last * 10 + 9;
    }
    return step;
}
int findKthNumber(int n, int k) {
    int cur = 1;
    k--;
    while (k > 0) {
        int step = getNode(cur, n);
        if (step <= k) {
            k -= step;
            cur++;	// 移动到i+1的节点上
        } else {
            k--;	// 移动到i节点的子节点上
            cur = cur * 10;    	
        }
    }
    return cur;
}