LC.P400[第N位数字]

方法一：模拟

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
class Solution {

    // 基本规律:
    // [1, 9]        有9 * 1个数字     => 9 * 1 * 1     => 9 * 10^0 * 1
    // [10, 99]      有90 * 2个数字    => 9 * 10 * 2    => 9 * 10^1 * 2
    // [100, 999]    有900 * 3个数字   => 9 * 100 * 3   => 9 * 10^2 * 3
    // [1000, 9999]  有9000 * 4个数字  => 9 * 1000 * 4  => 9 * 10^3 * 4
    //                                                 => 9 * 10^(n-1) * n
    // ...
    public int findNthDigit(int n) {
        // 确定第n位数的长度
        int len = 1;
        while (len * 9 * Math.pow(10, len - 1) < n) {
            n -= len * 9 * Math.pow(10, len - 1);
            ++len;
        }
        // 先得到起点值
        // len = 2时，s = 10
        // len = 3时，s = 100
        long s = (long) Math.pow(10, len - 1);
        s += n / len - 1;
        n -= len * (n / len);
        return n == 0 ? (int) (s % 10) : (int) ((s + 1) / Math.pow(10, len - n) % 10);
    }
}
  • 时间复杂度：$O(logn)$
  • 空间复杂度：$O(1)$