leetcode 400 Nth Digit
z
 2019-04-17 10:26:19  

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 < 231).

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
    2
    3
    4
    5
    6
    7
    8
    0		1		2		3		4		5		6		7		8		9			-> start = 0, width = 1, count = 9
    ---
    10	11	12	13	14	15	16	17	18	19		-> start = 10, width = 2, count = 90
    20	21	22	23	24	25	26	27	28	29
    ...
    90	91	92	93	94	95	96	97	98	99
    ---
    100	101	102	....													-> start = 100, width = 3, count = 900

  • 用start来保存每一个分组的开始的数组

  • 用width来保存每当前分组中，每一个数包涵几个数字

  • 用count来保存每一个分组中，一共有多少个数

  • 那么，每一个分组中，一共包含 count * width位数

  • 第一步，先找到n位于哪个分组，找到该分组的start

  • 第二步，找到n位于当前分组的那个数中

  • 第三步，确定n位是当前这数的第几个位

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findNthDigit(int n) {
        int start = 1;
        int step = 1;
        long count = 9;
        while (n > step * count) {
            n -= step * count;
            step += 1;
            count *= 10;
            start *= 10;
        }
        start += (n-1) / step; // n-1的目的是为了从0开始索引
        String num = String.valueOf(start);
        return num.charAt((n - 1) % step) - '0';
    }
}