題⽬描述

數字以 0123456789101112131415... 的格式作為⼀個字符序列，在這個序列中第 2 位（從下標 0 開始計算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此類題，請你輸出第 n 位對應的數字。

示例1

輸⼊：0
返回值：0

示例2
輸⼊：2
返回值：2

示例3
輸⼊：13
返回值：1

思路及解答

暴力法

通過逐步構造數字序列來找到第n位數字

public class Solution {
    public int findNthDigit(int n) {
        if (n < 0) return -1;
        if (n == 0) return 0; // 示例1特殊情況處理[2](@ref)
        
        StringBuilder sequence = new StringBuilder();
        int num = 0;
        
        // 逐步構建序列，直到長度超過n
        while (sequence.length() <= n) {
            sequence.append(num);
            num++;
        }
        
        // 返回第n位字符對應的數字值
        return sequence.charAt(n) - '0';
    }
}

• 時間複雜度：O(n)，需要構造長度至少為n的字符串
• 空間複雜度：O(n)，需要存儲構造的字符串序列

數學規律

利用數字位數分佈的數學規律，直接定位第n位所在的數字和具體位置

數字位數分佈規律：

• 1位數：0-9 → 10個數字 × 1位 = 10位
• 2位數：10-99 → 90個數字 × 2位 = 180位
• 3位數：100-999 → 900個數字 × 3位 = 2700位
• k位數：9×10ᵏ⁻¹個數字 × k位

public class Solution {
    public int findNthDigit(int n) {
        if (n < 0) return -1;
        if (n == 0) return 0;
        
        int digit = 1;              // 數字位數（1位、2位、3位...）
        long start = 1;             // 當前位數範圍的起始數字
        long count = 9;             // 當前位數範圍內的數字總位數
        
        // 步驟1：確定n所在的數字位數
        while (n > count) {
            n -= count;             // 減去前一個位數範圍的數字總位數
            digit++;                // 位數增加
            start *= 10;            // 起始數字擴大10倍
            count = 9L * digit * start; // 計算新的位數範圍內的總位數
        }
        
        // 步驟2：確定n所在的具體數字
        long num = start + (n - 1) / digit; // 計算目標數字
        
        // 步驟3：確定n在數字中的具體位置並返回
        return Long.toString(num).charAt((n - 1) % digit) - '0';
    }
}

• 時間複雜度：O(log₁₀n)，循環次數與n的位數成正比
• 空間複雜度：O(1)，只使用常數級別變量

添0補齊

假設所有數字都是i位數，通過給較短數字前面添0，使所有數字位數相同，簡化定位邏輯

public class Solution {
    public int findNthDigit(int n) {
        if (n < 0) return -1;
        if (n == 0) return 0;
        
        int i = 1; // 數字位數
        
        // 通過添0補齊，使所有數字都視為i位數
        while (i * Math.pow(10, i) < n) {
            n += Math.pow(10, i); // 添0增加的位數
            i++;
        }
        
        // 定位目標數字和具體位置
        String num = String.valueOf(n / i);
        return num.charAt(n % i) - '0';
    }
}

• 時間複雜度：O(log₁₀n)，與數學規律法相同
• 空間複雜度：O(1)，常數空間複雜度