440. K-th Smallest in Lexicographical Order

class Solution {
    public int findKthNumber(int n, int k) {
        int nth = 1; // 当前所在的节点是第 n 大的节点
        int prefix = 1;

        while (nth < k) {
            int nodeCount = getNodeCount(prefix, n); // 此处统计的节点数量包含当前节点
            if (k > nth + nodeCount - 1) {
                // 要寻找的数在右边的树中
                prefix++;
                nth += nodeCount; // 跳过当前子树
            } else {
                // 要寻找的数在当前子树中
                prefix *= 10;
                nth++; // 当前节点移动至左下角节点，所以 nth++
            }
        }

        // 跳出时 nth = k, 即找到第 k 小的数
        return prefix;
    }

    private int getNodeCount(int rootPrefix, int n) {
        int count = 0;

        long endPrefix = rootPrefix + 1; // exclusive
        long prefix = rootPrefix;
        while (prefix <= n) {
            count += Math.min(endPrefix, n + 1) - prefix; // n is inclusive, so use n + 1
            prefix *= 10;
            endPrefix *= 10;
        }

        return count;
    }
}

注意在计算节点数量过程中的数据越界问题，题目输入的数据最高为九次方。

References

440. K-th Smallest in Lexicographical Order