class Solution {
public:
int findNthDigit(int n) {
}
};
400. 第 N 位数字
给你一个整数 n ，请你在无限的整数序列 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...] 中找出并返回第 n 位上的数字。
示例 1：
输入：n = 3 输出：3
示例 2：
输入：n = 11 输出：0 解释：第 11 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是 0 ，它是 10 的一部分。
提示：
1 <= n <= 231 - 1原站题解
python3 解法, 执行用时: 36 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-13 12:57:35
# i位数的数字个数
dp = [0] * 11
for i in range(1, 11):
# 位数i*个数10 ** i - 10 ** (i - 1)
dp[i] = (10 ** i - 10 ** (i - 1)) * i
class Solution:
def findNthDigit(self, n: int) -> int:
# 先确定是几位数
first = cnt = 0
for x in range(1, 11):
if n > dp[x]:
n -= dp[x]
else:
first = 10 ** (x - 1)
cnt = x
break
# 在确定是哪个数
num = first + (n - 1) // cnt
# 计算其索引位置
j = n - (num - first) * cnt - 1
return int(str(num)[j])
python3 解法, 执行用时: 28 ms, 内存消耗: 14.9 MB, 提交时间: 2022-11-13 12:56:05
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