剑指offer-69、数字序列中某⼀位的数字 _

思路及解答暴力法通过逐步构造数字序列来找到第n位数字javapublic 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位javapublic 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使所有数字位数相同简化定位逻辑javapublic 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; }