400. 第 N 位数字
题目描述
把正整数 1, 2, 3, ... 按顺序首尾相接，写成一个无限长的数字串 123456789101112...。
输入整数 n，返回这个数字串中第 n 个数字。位置从 1 开始数。
示例 1
输入：n = 3 输出：3
解释：前 9 位就是 1 到 9，第 3 位是 3。
示例 2
输入：n = 11 输出：0
解释：第 10、11 位来自整数 10，第 11 位是 0。
数据范围
1 <= n <= 2^31 - 1
解题思路
按位数分组：1 位数 9 个共 9 位，2 位数 90 个共 180 位，d 位数 9·10^(d-1) 个共 d·9·10^(d-1) 位。先整组跳过，直到 n 落在某组内；组内每个数占 d 位，第 (n-1)//d 个数是 start + (n-1)//d，再取它的第 (n-1)%d 位。定位到组内哪个数这一步也可以用二分，但直接做除法就是一步到位的“二分”。
为什么正确
每次循环后，n 是在“所有 d 位及以上的数字串”中的位置，start 是最小的 d 位数。
复杂度分析
时间 O(log n)，空间 O(log n)（转字符串）。
易错点
n 可达 2^31 - 1，d·cnt 在 d=9 时是 81 亿，超过 32 位整数，C++/Java 要用 64 位。另外 n 要先减 1 再做除法和取模，否则在每个数的最后一位上会错一位。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findNthDigit(self, n: int) -> int:
d, cnt, start = 1, 9, 1
while n > d * cnt:
n -= d * cnt
d += 1
cnt *= 10
start *= 10
num = start + (n - 1) // d
return int(str(num)[(n - 1) % d])class Solution {
public int findNthDigit(int n) {
long d = 1, cnt = 9, start = 1, m = n;
while (m > d * cnt) {
m -= d * cnt;
d++;
cnt *= 10;
start *= 10;
}
long num = start + (m - 1) / d;
return Long.toString(num).charAt((int) ((m - 1) % d)) - '0';
}
}class Solution {
public:
int findNthDigit(int n) {
long long d = 1, cnt = 9, start = 1, m = n;
while (m > d * cnt) {
m -= d * cnt;
d++;
cnt *= 10;
start *= 10;
}
long long num = start + (m - 1) / d;
return to_string(num)[(m - 1) % d] - '0';
}
};func findNthDigit(n int) int {
d, cnt, start := 1, 9, 1
for n > d*cnt {
n -= d * cnt
d++
cnt *= 10
start *= 10
}
num := start + (n-1)/d
return int(strconv.Itoa(num)[(n-1)%d] - '0')
}var findNthDigit = function(n) {
let d = 1, cnt = 9, start = 1;
while (n > d * cnt) {
n -= d * cnt;
d++;
cnt *= 10;
start *= 10;
}
const num = start + Math.floor((n - 1) / d);
return Number(String(num)[(n - 1) % d]);
};function findNthDigit(n: number): number {
let d = 1, cnt = 9, start = 1;
while (n > d * cnt) {
n -= d * cnt;
d++;
cnt *= 10;
start *= 10;
}
const num = start + Math.floor((n - 1) / d);
return Number(String(num)[(n - 1) % d]);
}