LeetCode 400. 第 N 位数字
题目描述
给你一个整数 n，请你在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 中找出并返回第 n 位上的数字。
示例：n = 11，序列为 1 2 3 4 5 6 7 8 9 1 0 1 1 …，第 11 位是 0。
思路：按位数分组定位
把序列按数字位数分层：
层 数字范围 数字个数 该层总位数
1 位 1 ~ 9 9 9
2 位 10 ~ 99 90 180
3 位 100 ~ 999 900 2700
4 位 1000 ~ 9999 9000 36000
… … 9 × 10^(d-1) 9 × 10^(d-1) × d
步骤：
- 从 d = 1 开始，逐层减去总位数 9 × 10^(d-1) × d，直到 n 落进当前层。
- 此时 n 表示在当前层（d 位数）中的第 n 位（从 1 开始）。
- 当前层的起始数字是 start = 10^(d-1)。
- 第 n 位所在的数字：num = start + (n - 1) / d。
- 该数字中的第几位（从高位起，0 开始）：idx = (n - 1) % d。
- 答案即 num 的第 idx 位数字。
Java 实现
classSolution{publicintfindNthDigit(intn){// d：当前层的位数；start：当前层最小的 d 位数；count：当前层数字个数longd=1;longstart=1;longcount=9;// 逐层跳过，直到 n 落在当前层while(n>d*count){n-=d*count;// 减去当前层占用的位数d++;start*=10;count*=10;}// 现在 n 是当前层（d 位数）中的第 n 位（1-indexed）// 定位到具体数字longnum=start+(n-1)/d;// 定位到该数字中的具体位（从高位开始，0-indexed）intidx=(int)((n-1)%d);// 取 num 的第 idx 位// 例如 num = 1234, d = 4, idx = 0 → 要取最高位// (num / 10^(d-1-idx)) % 10return(int)(num/(long)Math.pow(10,d-1-idx)%10);}}关键点说明
- 为什么用 long？
n 最大可达 2^31 - 1（约 21 亿），d * count 在处理较大 d 时可能接近甚至超过 int 上限（如 d = 9 时 9 × 10^8 × 9 ≈ 8.1×10^9），用 long 保存 d、start、count 可避免溢出。
- 取位运算
假设 num = 1234，d = 4：
· idx = 0（最高位 1）：1234 / 10^3 % 10 = 1
· idx = 1（第二位 2）：1234 / 10^2 % 10 = 2
· idx = 3（最低位 4）：1234 / 10^0 % 10 = 4
- 也可以转成字符串取位
Strings=String.valueOf(num);returns.charAt(idx)-'0';可读性更好，但性能略差（有字符串创建开销）。面试中两种都接受，推荐算术法。
手算验证
以 n = 11 为例：
- 第 1 层（1 位数）：d = 1, count = 9, d*count = 9，11 > 9，跳过 → n = 11 - 9 = 2。
- 进入第 2 层：d = 2, start = 10, count = 90, d*count = 180，2 ≤ 180，停止。
- num = 10 + (2 - 1) / 2 = 10 + 0 = 10。
- idx = (2 - 1) % 2 = 1。
- num = 10 的第 1 位（0-indexed）为 0。✅
再验证 n = 1：
- d=1, count=9, d*count=9，1 ≤ 9，不跳过。
- num = 1 + (1-1)/1 = 1，idx = (1-1)%1 = 0，返回 1。✅
复杂度分析
· 时间复杂度：O(log n)，循环次数等于 n 对应的数字位数（最多约 10 次）。
· 空间复杂度：O(1)，仅使用常数额外空间。
这是本题的最优解法，也是官方推荐的数学推导法。
