class Solution {
public:
int findNthDigit(int n) {
}
};
剑指 Offer 44. 数字序列中某一位的数字
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中，第5位（从下标0开始计数）是5，第13位是1，第19位是4，等等。
请写一个函数，求任意第n位对应的数字。
示例 1：
输入：n = 3 输出：3
示例 2：
输入：n = 11 输出：0
限制：
0 <= n < 2^31注意：本题与主站 400 题相同：https://leetcode.cn/problems/nth-digit/
原站题解
python3 解法, 执行用时: 32 ms, 内存消耗: 15 MB, 提交时间: 2022-11-13 12:55:48
class Solution:
def totalDigits(self, length: int) -> int:
digits = 0
curCount = 9
for curLength in range(1, length + 1):
digits += curLength * curCount
curCount *= 10
return digits
def findNthDigit(self, n: int) -> int:
low, high = 1, 9
while low < high:
mid = (low + high) // 2
if self.totalDigits(mid) < n:
low = mid + 1
else:
high = mid
d = low
prevDigits = self.totalDigits(d - 1)
index = n - prevDigits - 1
start = 10 ** (d - 1)
num = start + index // d
digitIndex = index % d
return num // 10 ** (d - digitIndex - 1) % 10
python3 解法, 执行用时: 28 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-13 12:55:05
class Solution:
def findNthDigit(self, n: int) -> int:
d, count = 1, 9
while n > d * count:
n -= d * count
d += 1
count *= 10
index = n - 1
start = 10 ** (d - 1)
num = start + index // d
digitIndex = index % d
return num // 10 ** (d - digitIndex - 1) % 10