题解 | #数字序列中某一位的数字#

#include <string>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param n int整型
     * @return int整型
     */
    int findNthDigit(int n) {
        if (n == 0) {
            return 0;
        }
        // 从1位数开始算起
        // 1位数中抛开0所占的数位数是9
        // k(k>1)位数所占的数位数 = 9 * pow(10,k) * k
     
        int k = 1; // 当前数位量级
        //下面两个变量要设置为long类型，否则会出现数据溢出的问题。
        long long sum = 9; // 当前数位的数字个数
        long long  start = 1; //当前数位的初始数字
        while (n > sum) {
            n -=  sum;
            k++;
            start = start * 10;
            sum = 9 * start * k;
        }
        // 此时n<=sum. 表明第n位数字所在的数是k位数，
        int num = start + (n-1) / k;
        int digitIndex = (n-1) % k;
        return to_string(num)[digitIndex] - '0';


    }
};

每一道题需要最后形成一个连贯的逻辑，题目有关键点。解决每一个关键点的方法是什么？

关键点一：第n位(下标从0开始算起)数字所在的数是几位数？

注：由于下标从0开始算起，很自然就忽略掉了0. 所以可以将n当做去掉0之后从1开始算起的下标。

判断方法：需要知道前k位数字所占的数位数目，那就需要知道第i(i = 1,2,3,...)位数字所占的数位数，然后进行累加，判断n-已经累加过的数位数的剩余数位数是否超过当前数位所占的数位数。

关键点二：假设第n位数字所在的数是k0位数，那么k0位数的起始数字是多少？第n位数字所在的数是k0位数中的第几个数字？假设这个数为num, 第n位数字位于num的第几位？

判断方法：k0位数的起始数字是1 pow(10, k0-1) := start

(n - 前(k0-1)位数所占的位数总和) / k0, 就是该数字的编号, 记作index

num = start + index

设第n位数字位于num的digitIndex位，则digitIndex = (n - 前(k0-1)位数所占的位数总和) % k0