题目
给你一个整数 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
解答
- 暴力解决
class Solution {
public:
int findNthDigit(int n) {
int d = 1, count = 9;
while (n > (long) d * count) {
n -= d * count;
d++;
count *= 10;
}
int index = n - 1;
int start = (int) pow(10, d - 1);
int num = start + index / d;
int digitIndex = index % d;
int digit = (num / (int) (pow(10, d - digitIndex - 1))) % 10;
return digit;
}
};
- 直接计算
class Solution {
public:
int findNthDigit(int n) {
long base = 9, digits = 1;
// 第一步：确定 n 所在的数字有几位
while (n - base * digits > 0) {
n -= base * digits;
base *= 10;
digits++;
}
// 第二步：确定 n 所在的具体数字
int index = n % digits;
if (index == 0) index = digits;
long number = 1;
for (int i = 1; i < digits; i++) {
number *= 10;
}
number += (index == digits) ? n/digits - 1 : n/digits;
// 第三步：找到并返回目标数字中的具体一位
for (int i = index; i < digits; i++) number /= 10;
return number % 10;
}
};