💡题目：字典序的第K个数字

下面是一个经典的字典数（字典序）相关代码题，适合用来考察排序、递归或生成全排列等能力。

好的，下面是一个经典的字典数（字典序）相关代码题，适合用来考察排序、递归或生成全排列等能力。

---

💡题目：字典序的第K个数字

给定两个整数 n 和 k，返回从1到n的字典序中第k小的数字。

📘示例

输入: n = 13, k = 2
输出: 10
解释: 从1到13的字典序如下：
["1","10","11","12","13","2","3","4","5","6","7","8","9"]
第2个字典序是 "10"

---

✅要求

• 1 <= k <= n <= 10^9
• 时间复杂度不能是 O(n)，因为 n 很大

---

🔍思路

将数字视为一棵字典树（Trie），遍历的时候按照字典序前序遍历：

        ""
     / / \ \ \ ...
    1 2   3 4 5 ...
   /|\
 10 11 12 ...

我们每次判断以当前节点为前缀的数字共有多少个（例如以1开头的是：[1,10,11,12,13]，共5个），用这个数量判断跳不跳。

---

✅Python 代码实现：

def findKthNumber(n: int, k: int) -> int:
    def get_steps(curr, n):
        steps = 0
        first = curr
        last = curr
        while first <= n:
            steps += min(last, n) - first + 1
            first *= 10
            last = last * 10 + 9
        return steps

    curr = 1
    k -= 1  # 从1开始，所以先减1
    while k > 0:
        steps = get_steps(curr, n)
        if steps <= k:
            k -= steps
            curr += 1
        else:
            curr *= 10
            k -= 1
    return curr

---

🧪测试用例：

print(findKthNumber(13, 2))  # 输出 10
print(findKthNumber(100, 10))  # 输出 17