算法与数据结构

题目描述

数字以 0123456789101112131415... 的格式作为一个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。

示例1

输入：0
返回值：0

示例2

输入：2
返回值：2

示例3

输入：13
返回值：1

思路 & 解答

这道题是数学规律题，先找到规律，下面是几个区间

1. 小于10，1~9，9个数字，9位
1. 大于等于10小于100，10~99，90个数字，180位
1. 大于等于100且小于1000，100~999，900个数字，2700位
2. ......

当我们查找第 n 为位的时候，需要先计算出 n 落在哪一个区间内，比如 8 就在第一个区间内，161 就在第二个区间内，1314 就在第 3 个区间内；

计算出区间之后，需要计算出所在的数字是哪一个，比如 1314 （一共4位），然后再计算位数。

Java 代码实现如下：

public class Solution44 {
    public int findNthDigit (int n) {
        if (n <= 0) return 0;
        // 开始数值
        long start = 1;
        // 位数
        long digit = 1;
        // 个数
        long count = 9;

        while (n > count) {
            n -= count;
            start *= 10;
            digit += 1;
            count = start * 9 * digit;
        }
        // 所在的数字
        String num = (start + (n - 1) / digit) + "";
        // 计算位数（第几个数字）
        int index = (int)((n - 1) % digit);
        return Integer.parseInt(num.charAt(index) + "");
    }
}

C++ 代码如下：

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return int整型
     */
    int findNthDigit(int n) {
        if (n <= 0) return 0;
        // 开始数值
        long start = 1;
        // 位数
        long digit = 1;
        // 个数
        long count = 9;

        while (n > count) {
            n -= count;
            start *= 10;
            digit += 1;
            count = start * 9 * digit;
        }
        // 所在的数字
        string num = to_string(start + (n - 1) / digit) + "";
        // 计算位数（第几个数字）
        int index = (int) ((n - 1) % digit);
        return num[index] - '0';
    }
};