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

题目描述

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

分析

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

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

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

例如,$ 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 + 36000 $$ $$ =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 / mn % 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