题目链接

LeetCode

题目描述

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

解题思路

方法一：字典树（十叉树）

class Solution {
    public int findKthNumber(int n, int k) {
        // 当前字典树结点 (当前遍历到的数字)
        int cur = 1;
        // 到达第 k 个节点需要遍历 k-1 个结点 
        // 当前 k 值表示剩余需要遍历的节点数 
        k -= 1;
        while(k > 0){
            int nodes = getNodes(n, cur);
            // 如果当前子树的结点数小于等于 k， 则需要全部遍历
            if(nodes <= k){ // 向右侧节点走
                // 减去已经遍历过的子树
                k -= nodes;
                // 指向下一个新的结点
                ++cur;
            }else{ // 向下往最左孩子节点走:字典序上升1位
                // 结果在当前子树中, 减去当前根节点
                --k;
                // 向下一层搜索
                cur *= 10;
            }
        }
        return (int)cur; // 最后cur停在的数字就是字典序的第K小数字
    }
    // 获取 cur 值下子树结点的个数
    private int getNodes(int n, long cur){
        long nodes = 0;
        long next = cur + 1;
        while(cur <= n){
            // 如果当前一层中有定值 n， 则只能取到n，末位从 0 开始
            nodes += Math.min(n - cur + 1, next - cur);
            // 计算下一层个数
            next *= 10;
            cur *= 10;
        }
        // 返回当前 cur 值下子树结点个数
        return (int)nodes;
    }
}

• 时间复杂度 O(log n)
• 空间复杂度 O(1)