leetcode-400-Nth-Digit

描述


Find the $n^{th}$ 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 < 2^{31}).

Example 1:

1
2
3
4
5
Input:
3

Output:
3

Example 2:

1
2
3
4
5
6
7
8
Input:
11

Output:
0

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.

分析


解决方案1(C++)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
int findNthDigit(int n) {
long long len_n = 1, count = 9, start = 1;
while (n > len_n * count) {
n -= len_n * count;
len_n++;
count *= 10;
start *= 10;
}

start += (n-1) / len_n;
string result = to_string(start);
return result[(n-1)%len_n] - '0';
}
};

解决方案2(Java)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
public int findNthDigit(int n) {
int now_len = 1;
long pre_count = 9;
int start_count = 1;
int digit_num;

while(n > now_len*pre_count) {
n -= now_len*pre_count;
now_len += 1;
pre_count *= 10;
start_count *= 10;
}
digit_num = start_count + (n-1)/now_len;
String num_str = Integer.toString(digit_num);
return Character.getNumericValue(num_str.charAt((n-1)%now_len));
}
}

解决方案3(Python)


1
2
3
4
5
6
7
8
9
10
11
class Solution:
def findNthDigit(self, n: int) -> int:
now_len, count, start = 1, 9, 1
while (n > now_len * count):
n -= now_len * count
now_len = now_len + 1
count = count * 10
start = start * 10
start += (n-1) / now_len
result = str(start)
return result[(n-1)%now_len]

题目来源