题⽬描述
数字以 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;// 逐步构建序列，直到长度超过nwhile (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)，常数空间复杂度