LeetCode Nth Digit
Find the nth digit of the infinite integer sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …
Note:
n is positive and will fit within the range of a 32-bit signed integer (n < 231).
Example 1:
Input:
3
Output:
3
Example 2:
Input:
11
Output:
Explanation:
The 11th digit of the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... is a 0, which is part of the number 10.
自然数的连续序列中，第n个数字是什么。
简单的数学题，没有捷径，直接统计吧。
- 1~9：宽度为1，数字个数1*9
- 10~99：宽度为2，数字个数2*90
- 100~999：宽度为3，数字个数3*900
- …
首先不断累加1*9+2*90+3*900+…+k*9*pow(10,k-1)直到和大于n时停止，此时能定位到第n个数字所在的数的宽度width以及该宽度的第一个数start。然后计算在该宽度范围内，偏移了几个数字leftdigit=n-{1*9+2*90+…+(k-1)*9*pow(10,k-2)}。根据leftdigit和width又能定位到原始第n个数字所在的数target以及第n个数字在target中的第几个位置pos。最后把target转换为string取出第pos位数字即可。
代码如下，注意要把代码中的变量都定义为long long，否则大数可能溢出。
[cpp]
class Solution {
public:
int findNthDigit(int n) {
long long width = 1, start = 1, num = 9;
while (n > num) {
++width;
start *= 10;
num += width * 9 * start;
}
long long leftdigit = n – (num – width * 9 * start);
long long offset = leftdigit / width + ((leftdigit%width == 0) ? 0 : 1);
long long target = start + offset – 1, pos = leftdigit%width;
if (pos == 0)pos = width;
string s = to_string(target);
char c = s[pos – 1];
return atoi(&c);
}
};
[/cpp]
本代码提交AC，用时3MS。
最后定位到target之后，不转换成string，直接用除法和取模运算也能得到第pos位数字，代码如下：
[cpp]
class Solution {
public:
int findNthDigit(int n) {
long long width = 1, start = 1, num = 9;
while (n > num) {
++width;
start *= 10;
num += width * 9 * start;
}
long long leftdigit = n – (num – width * 9 * start);
long long offset = leftdigit / width + ((leftdigit%width == 0) ? 0 : 1);
long long target = start + offset – 1, pos = leftdigit%width;
if (pos == 0)pos = width;
int cnt = 0, ans;
while (cnt < pos) {
ans = target / start;
target -= ans*start;
start /= 10;
++cnt;
}
return ans;
}
};
[/cpp]
本代码提交AC，用时6MS。]]>