数字序列中某一位的数字（C++）

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

数据范围： 0≤n≤10⁹

输入：
0
返回值：
0

输入：
2
返回值：
2

输入：
10
返回值：
1

输入：
13
返回值：
1

参照牛客网：君无颜（https://www.nowcoder.com/profile/686280659）的解法。

  当 0<=n<=9时，这个题很简单，因为位置是对应的，问题就出在 后面的数字导致了位数的变化。

  那我们的核心观点就是，让这个位数 保持一致。

  后面的我们没法动，那最简单的方法就是，动前面的：

0|1|2|3|4|5|6|7|8|9|10

  改成

00|01|02|03|04|05|06|07|08|09|10

  此时，这个题就瞬间变的简单多了,这个时候，我们的总位数增加了10个（0-9），所以我们的目标位往后挪了10位。

class Solution {
  public:
    
    int findNthDigit(int n) {
        if (n >= 0 && n <= 9)
            return n;
        int i = 2;
        //i*pow(10*i)是为了限制i++一次。
        //同时i*pow(10*i)也表示当前的位数，如果i=1，表示最小单元为1位，而i=2表示最小单元为2位（因为一位的数前面都添加了一个0）
        //如果n = 13，那么n在1*10^1 <= n+10 <= 2*10^2的区间
        while (i * pow(10, i) < n) {
            n += pow(10, i);
            i++;
        }
        return to_string(n / i)[n % i] - '0';
    }

};

举个例子：n=13

这个应该是数字11的第二个1（可以自己数数）。

那么当位置往后挪了10个，我们目标就变成了：23 （13+10）。

如果n是一个三位数，那么（00-99）都要在前面再加个0，变成（000-099），所以我们会再往后挪100（即10^2） 位。

此时，我们已经可以通过除法，找到我们的目标数字。

譬如刚才的例子：n=13，通过一个一个数，我们可以得知，是数字11的第二个1，但是当所有数字补齐位数之后，我们知道现在所有数字都是两位，23/2=11,我们通过当前位置/位数得到了目标数字target_num（其实就是所有数字位数都一样，整除一下位数，就可以知道是在第几个数）。

然后我们再通过取模，知道是在target_num的哪位上，即num_place。

注：

• target_num = n//i
• num_place = n%i

该方式恰好与方式一相反，如下

1-9  9`个*1
10-99  90个*2
100-999  900个*3
1000-9999 9000个*4

针对不同的数，所占位数不同。

我们将其分为不同的区间，符合要求的区间我们将其进行剔除，直至不符合下一个要求的区间为止。

class Solution {
  public:
    
    int findNthDigit(int n) {
        // write code here
        if(n>=0 && n<= 9)return n;
        long long start = 1;//起始数
        long long digital = 1;//记录当前所在区间
        long long count = 9;//记录当前区间数
        //减去前面区间的数
        while(n > count)
        {
            digital++;
            n -= count;
            start *= 10;
            count = digital * start * 9;
        }
        //以下为n剩余的数
        //先判断剩余的n是在哪个数
        long long number = start + (n - 1)/digital;//start就是开始的第一个数字，所以后面要n-1
        //判断是这个数的哪一位
        long long index = (n-1)%digital;
        //得出结果
        return to_string(number)[index] - '0';
    }
};