题目描述

在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。

注意:
n 是正数且在32位整数范围内 ( n < 231)。

示例 1:
输入:
3
输出:
3

将整个过程拆解，分为三个部分
输入n
1.求n所落在的数值的位数,如 13 落在【10-99】区间
2.求所在数值x是多少和对应数值x的第几位，如第13位对应数值11的第二位

#include<string>

using namespace  std;


class Solution {
public:
    int findNthDigit(int n) {
        //找规律的题目需要非常非常非常耐心
        long digit = 1,start = 1,count = 9;
        // 确定所求的数是几位数
        while(n > count){
            n -= count;
            start *= 10; //1,10,100
            digit += 1;  //1,2,3
            count = 9 * start * digit;
        }
        //设置start后简单很多
        long num = start + (n-1)/digit;
        int res = int(to_string(num)[(n-1) % digit] - '0');
        return res;
    }
};