解題說明
K-th Smallest in Lexicographic Order
題目描述：給定整數 n 和 k，求 1 到 n 中字典序第 k 小的整數。例如 n = 13，k = 2，字典序為 [1, 10, 11, 12, 13, 2, 3, ...]，第 2 小為 10。
解題思路：將 1n 想像成 10 叉 Trie，字典序第 k 小等同於前序遍歷的第 k 個節點。關鍵在於能快速計算「以 n 中以 prefix 為根的子樹共有多少個節點（即 1prefix 為前綴的數字數量）」，此函式稱為 countSteps(n, prefix)。
countSteps 計算方式：
- 設
cur = prefix，next = prefix + 1（下一個兄弟前綴）。 - 每一層累加
min(n+1, next) - cur（該層中以prefix為前綴的有效數字數）。 - 然後
cur *= 10，next *= 10，往下一層移動。 - 直到
cur > n停止。
主迴圈貪心策略：
- 從
cur = 1開始，k--（自身算一個）。 - 計算以
cur為前綴的子樹大小steps。 - 若
steps <= k：答案不在此子樹，跳過整棵子樹，cur++（往兄弟走），k -= steps。 - 若
steps > k：答案在此子樹，往下一層，cur *= 10，k--（進入子節點算一步）。 - 當
k == 0時，cur即為答案。
C++ 解法
複雜度分析
時間複雜度：O((log n)²) — 外層迴圈最多走 O(log n) 步（Trie 深度），每次呼叫 countSteps 也需 O(log n) 層迭代，總體為 O((log n)²)。
空間複雜度：O(1) — 只用常數個輔助變數，無需額外空間。
虛擬碼
1. Define countSteps(n, cur, next):
a. steps = 0
b. While cur <= n:
- steps += min(n+1, next) - cur
- cur *= 10, next *= 10
c. Return steps.
2. cur = 1, k = k - 1.
3. While k > 0:
a. steps = countSteps(n, cur, cur+1).
b. If steps <= k: k -= steps; cur += 1 (skip subtree).
c. Else: k -= 1; cur *= 10 (go deeper into subtree).
4. Return cur.其他解法
方法二：生成全部字典序後取第 k 個
利用 LC 386 的 O(n) 演算法生成 1~n 的字典序陣列，直接取第 k 個元素。時間 O(n)，空間 O(n)。當 n 很大時（如 10⁹）需儲存所有元素，不可行；本題最優解 O((log n)²) 遠勝於此。
方法三：字串排序
將 1~n 所有數字轉字串排序，取第 k 個再轉回整數。時間 O(n log n)，空間 O(n · d)。完全不符合 n 可達 10⁹ 的限制，僅作為概念驗證。
方法四：二分搜尋前綴
對每一位元的選擇（前綴的下一位 0~9）用二分搜尋確定。本質上與貪心 + countSteps 方法相同，只是用二分取代逐位決策。在此場景下貪心已是最優，二分多此一舉。
延伸思考
- 若
n的範圍擴展到 10^18，上述countSteps中使用long long是否足夠？乘以 10 時有溢位風險，如何安全處理？ - 若改為找字典序第 k 大的數字（而非第 k 小），演算法需要做哪些對稱性修改？
countSteps計算的是 Trie 子樹大小，這與「統計 1~n 中以某字串s為前綴的數字數量」問題完全等價，能否將此技巧推廣到任意進位（如二進位 Trie）？