剑指 Offer-44 数字序列中某一位的数字

发表于 | 分类于 | 评论数： | 阅读次数：

题目链接： 剑指 Offer-44

题目描述：

数字以 0123456789101112131415… 的格式序列化到一个字符序列中。在这个序列中，第 5 位（从下标 0 开始计数）是 5，第 13 位是 1，第 19 位是 4，等等。

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

解题思路：

  1. 首先我们将这个序列分段，分段的依据是序列中数字的位数 digit。即：1-9 为一段，10-99为一段，100-999 为一段，一次类推。每一段中数字的位数记为 digit。
  2. 然后再从下面的表格中寻找规律
数字范围 位数 数字个数 段长度
1~9 1 9 9
10-99 2 90 2*90
100-999 3 900 3*900
… … … …
start~end digit 9 * start \(9 *digit * start\)

即：每一段中数字个数都是 \(9*10^{digit-1}\) 这么多数字，然后我们发现，\(10^{digit-1}\) 又恰好等于，每一段中的第一个数字。那么由每一段所组成的字符串长度就可以得到了\(l_{digit}=9 * start*digit\)。

  1. 所以只要循环用 n 减去所有的 \(l_{digit}\) 直到 \(n<l_{digit}\)， 那么 n 就是个 digit 位数。然后就要确定，n 位于这个段中的哪个数字，可以从下面的式子中求得 ：（这一段中每个数字的长度都相同）

    1
    cand_num = start_num + (n-1/digit)

  2. 最后一步就是确定，这个 n 是 cand_num 中的第几位数字，取模就好。

    1
    dn = (n-1)%digit

    然后再取出 cand_num 从左往右的第 dn 位。

    1
    res = str(cand_num).at(dn)-'0'

代码

最后总的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution{
    public int findNthDight(int n){
        int start = 1; // 每段的起始数字
        int digit = 1; // 每段每个数字的长度
        int count = 9; // 每段数字个数
        while(n> count){
            n -= count;
            digit+=1;
            start*=10;
            count = 9*start*digit;
      	}
        int num = start + (n-1)/digit;
        int res = Integer.toString(num).charAt( (n-1)%digit )-'0';
        return res;
    }
}