这道题目和《剑指 Offer 之 从整数 1 到 n 中 1 出现的次数》是一样的，也是通过寻找数字序列的规律解决的。

题目描述

数字以 0123456789101112131415...... 的格式序列化到一个字符序列中。在这个序列中，第 5 位（从 0 开始计数）对应的数字是 5，第 13 位对应的数字是 1，第 15 位对应的数字是 2。请写一个函数，求任意第 n 位对应的数字。

分析

这里就不再重复剑指 Offer 中的方法了，而是直接通过数字的规律来解决这道题。

令 $ f(x) $ 表示从 0 到 x 所占位数的最大数字 的数字个数。（特别注意断句的含义！）

怎么理解这句话呢？举个栗子 : )

例如，$ f(1) $ 的计算过程如下：

$$ f(1) = (0\sim9) $$ $$ = (9-0+1)×1 $$ $$ = 10 $$

则数字的个数就是 10 个 （乘以 1 是因为从 0 到 9 每个数字对应的位数是 1 位）；

同样的，$ f(2) $ 的计算过程如下：

$$ f(2) =(0\sim9)+ (10\sim99) $$ $$ = f(1) +(99-10+1)×2 $$ $$ = 10 +90×2$$ $$ = 190 $$

则数字的个数就是 190 个 （乘以 2 是因为从 10 到 99 每个数字对应两位数，例如 11 是两个数，即 1 和 1；12 也是两个数，即 1 和 2；98 是两位数，即 9 和 8；99 是两位数，即 9 和 9），190 就是将它们拆开，共同统计 个数 所得到的结果；

同样的，$ f(3) $ 的计算过程如下：

$$ f(3) =(0\sim9)+ (10\sim99)+ (100\sim999) $$ $$ = f(2) + (999-100+1)×3 $$ $$ = 190 + 900×3 $$ $$ = 2890 $$

同样的，$ f(4) $ 的计算过程如下：

$$ f(4) =(0\sim9)+ (10\sim99)+ (100\sim999) + (1000\sim9999)$$ $$ =f(3) + (9999-1000+1)×4 $$ $$ = 2890 + 9000×4 $$ $$ =38890 $$

因此，我们可以总结出以下规律：

$$ f(x)=f(x-1)+(9×10^{x-1}) × x $$

明白了上面的关系之后，后面的计算就简单多了。

对于数字 n，我们比较其与 arr[] 数组中的元素，如果 f(m)>=n，则说明我们在数组中找到了第一个大于 n 的值，则 n 就在某个 m 位数的其中一位。

所以，可以用 n = n - f(m - 1 )，根据 n / m 与 n % m 的值，就可以确定数字 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
26
27
28

public class Solution {
    public int digitsInSequence(int arr[], int n) {
        if (n < 0) return -1;
        if (n <= 9) return n;

        int m = 0;
        for (int i = 1; i <= 9; i++) {
            if (arr[i] >= n) {
                m = i;
                break;
            }
        }

        n = n - arr[m - 1];
        int temp1 = n / m;
        int temp2 = n % m;
        int temp3 = (int) (temp1 + Math.pow(10, m - 1));
        return (int) (temp3 / Math.pow(10, m - temp2 - 1)) % 10;
    }

    public static void main(String[] args) {
        // 由于 int 装不下 8888888890 这个数，所以没有将其放到数组里
        int[] arr = {0, 10, 190, 2890, 38890, 488890, 5888890, 68888890, 788888890}; 
        Solution solution = new Solution();
        int i = solution.digitsInSequence(arr, 1001);
        System.out.println(i);
    }
}

真是让人抓狂的一道题，不过理解了解题过程之后，心里也会有一丢丢的成就感~ 😄

参考

https://www.cnblogs.com/wangkundentisy/p/8920147.html