题目描述

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。

在这个序列中，第 5 位（从 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。

请写一个函数求任意位对应的数字。

时间复杂度

logn

思路

0 - 9 的时候直接返回 n
两位数 10 - 99 一共有 90个数，一共有 90 * 2 位;
三位数 100 - 999 一共有 900 个数，一共有900 * 3 位；
n 位数 10^(n - 1) - 10 ^n 一共有9 * 10^(n - 1)个数,一共有9 * 10 ^(n - 1) * n位;
因此，确定n对应的数字是几位数，然后求出来之后，除以n位数，求商a,余b, n位数的开始的第一个数是10^(n - 1)
之后便可以确定n位数对应的数字是 res :10^(n - 1) + a;如果 b == 0 表示是res 对应前一个数的最后一位，所以返回 (res - 1) % 10;
如果b不是0 ，那结果对应的应该是res 从高位到低位的第b位,对应的是从低位到高位的第(n - b + 1)位， 返回 res / 10 ^(n - b) % 10;

编程tips

当确定n 的位数的时候，要计算n位数对应的位数 就是上面提到的 9 * 10 ^(n - 1) * n位，会出现int 越界的情况，因此需要用long来存；

Java 代码

class Solution {
    public int digitAtIndex(int n) {
        if(n <= 9) return n;
        int bit = 1;
        long sum = 0;
        n = n -9;
        while(n > sum)
        {
            n -= sum;
            bit ++;
            sum = (long)Math.pow(10,(bit - 1))*9 * bit;
        }
        int a = n / bit;
        int b = n % bit;
        int res = (int)Math.pow(10,(bit - 1)) + a;
        if(b == 0) return (res - 1) % 10;
        else return res /(int)Math.pow(10,(bit - b)) % 10;
    }
}