解題說明
Nth Digit
題目描述：給定正整數 n，在無限整數序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 中找出第 n 個數字（digit）。
解題思路：將數字依位數分段：1 位數有 9 個（1–9），共 9 digits；2 位數有 90 個（10–99），共 180 digits；k 位數有 9×10^(k-1) 個數字，共 k×9×10^(k-1) digits。逐段扣除 n，找到 n 落在哪個位數範圍，再計算是哪個實際數字，最後取出對應位上的數字。
C++ 解法
複雜度分析
時間複雜度：O(log n) — 外層迴圈每次 digits 加 1，最多執行 O(log n) 次（因為 k 位數能容納的 digit 總數呈指數成長）。
空間複雜度：O(log n) — to_string(num) 所需字串長度與位數成正比。
虛擬碼
1. Initialize digits=1, start=1, count=9 2. While n > digits * count: - Subtract digits * count from n - Increment digits, multiply start and count by 10 3. Compute num = start + (n-1) / digits 4. Compute digitIndex = (n-1) % digits 5. Convert num to string, return character at digitIndex as integer
其他解法
二分搜尋法：對第 n 個 digit 對應的數字範圍做二分搜尋，可以同樣達到 O(log n)，但實作較繁瑣。
暴力法：從 1 開始逐個數字計算 digit 數並累減，直到 n <= 0。時間複雜度 O(n)，對大 n 不可行。
延伸思考
- 如果序列改為只包含偶數（2, 4, 6, ...），如何找第 n 個 digit？
- 若序列改為 Fibonacci 數列，能用同樣的分段策略嗎？
- 如何反向求解：給定一個 digit 值，找出所有可能的位置 n？