剑指offer 45- 数字序列中某一位的数字

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

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

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

输入：13

输出：1

分析：
（1）确定是几位数：n-10-902-9003
（2）确定n位数属于哪一个数
（3）确定属于那个数的第几位
时间复杂度：

class Solution {
public:
    int digitAtIndex(int n) {
        if(!n) return 0;
        //i表示是几位数，s表示i位数共有多少个，base表示i位数的起始值。
        long long i = 1, s = 9, base = 1; 
        // 9, 90, 900, 9000, 90000, i * s表示i位数总共占多少位。
        // 1000 - 9 - 90 * 2 - 900 * 3 ,当i= 3 时不符合条件，说明是在三位数里面。
        while(n > i*s) {
            n-=i*s;     
            i++;
            s*=10;
            base*=10;
        }
        //求i位数的第几个数，
        //1000 - 9 - 180 = n , n / 3 + base - 1（考虑0故减1）, 向上取整（n + i - 1）/i
        int number = base + (n+i-1)/i - 1; 
        // 除不尽就是第几位，除尽了就是最后一位。
        int r = n%i ? n%i : i;
        //求数的第i - r位，取出i - r位
        for(int j=0;j<i-r;j++) number/=10;
        return number % 10;
    }
};