400. Nth Digit 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int findNthDigit(int n) {
        long numStart = 1, numEnd = 9; // [start, end]
        int width = 1;
        long nStart = 1, nEnd = 9; // [nStart, nEnd]

        while (n > nEnd) {
            numStart *= 10;
            numEnd = numEnd * 10 + 9;

            width++;

            nStart = nEnd + 1;
            nEnd = nStart + (numEnd - numStart + 1) * width - 1;
        }

        // now: n <= nEnd and n >= nStart

        long digitOffset = n - nStart;
        long numOffset = digitOffset / width;
        long reminder = digitOffset % width;
        long divideTimes = width - reminder - 1;

        long res = numStart + numOffset;
        while (divideTimes > 0) {
            res /= 10;
            divideTimes--;
        }
        return (int)(res % 10);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findNthDigit(int n) {
        int digitCount = 1;
        long start = 1;
        long numCount = 9;

        while (n > numCount) {
            // 可以批量减去一部分数字
            n -= numCount;
            start *= 10;
            digitCount++;

            numCount = 9 * digitCount * start;
        }

        Long num = start + ((n - 1) / digitCount); // 定位所属整数
        return String.valueOf(num).charAt((n - 1) % digitCount) - '0';
    }
}

注意潜在的整数越界问题。

References

400. Nth Digit
剑指 Offer 44. 数字序列中某一位的数字