# LeetCode-Alg-400-Nth-Digit

## LeetCode-Alg-400-Nth-Digit

Posted by Jae on June 18, 2019

### 1、题目

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:
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.


### 2、思路

1 2 3 4 5 6 7 8 9 总共 9*1位
10 11 ...      99 总共 90*2位
100 101 ...   999 总共 900*3位
... 所以我们只需要找到n会落在那个区间就能找到第n位对应的数字， 对于第一行范围为[1, 9]，第二行范围[10, 189](90*2+9*1),第三行范围[190, 2889](900*3+90*2+9*1)...


### 3、实现

public class Solution {
public int findNthDigit(int n) {
int left = 0;
int right = left;
for (int i = 0; ; i++){
left = right + 1;
right += Math.pow(10, i) * 9 * (i + 1);
if (n >= left && n <= right){
// 位数是i+1
int head = (int)Math.pow(10, i);
// 差值
int diff = n - left;
// 已经找到
int target = head + diff / (i + 1);
// 取特定的一位
return String.valueOf(target).charAt(diff % (i + 1)) - '0';
}
}
}
}


< script src = " / js / bootstrap.min.js " >