题目来源

• leetcode

题目描述

题目解析

就是把逗号去掉一个一个数嘛，比如11，其实是1234567891011…字符串第11个，就是0啦，当然用这个逻辑写代码会超时）

主要有两步：

• 首先找到这个数字对应的数是几位数，用 digits 表示；
• 然后确定这个对应的数的数值 target；
• 最后确定返回值是 target 中的哪个数字。

（1）找到这个数字对应的数是几位数

找规律：

• 我们知道0~9是一位数，一位数一共有9个，总计产生9 * 1 = 9 位数字
• 我们知道 10-99 是两位数， 两位数共有90个， 总计产生 90 * 2 = 180 位数字
• 我们知道 100-999 是三位数， 三位数共有900个， 总计产生 900 * 3 = 1800 位数字
• …
• 以此类推，我们可以把digit位数里产生的数字个数算出来它等于$9\ast 10^{digit-1}\ast digit$

由此通过一个循环，对不同位数一共产生了多少个数字做累积并与n比较，我们就可以判断出n对应的数字是几位

举个例子：比如365

1. 经过第一步计算我们可以得到第 365 个数字表示的数是三位数，n=365−9−90×2=176，digtis = 3。这时 n=176表示目标数字是三位数中的第 176 个数字。
2. 我们设目标数字所在的数为 number，计算得到 number=100+176/3=158，idx 是目标数字在 number 中的索引，如果 idx = 0，表示目标数字是 number - 1 中的最后一个数字
3. 根据步骤2，我们可以计算得到 idx = n % digits = 176 % 3 = 2，说明目标数字应该是 number = 158 中的第二个数字，即输出为 5

实例2：

class Solution {
public:
	int findNthDigit(int n) {
		long cnt = 9, start = 1, digit = 1;   //因为可能会溢出
		//1、确定是在哪一个区间：字符数
		while (n > cnt * digit)  //当前区间字符数为 = 区间位数 * 区间字符个数，如果要找的字符数大于当前区间的总字符位数，进入下一区间查找
		{
			n -= cnt * digit;  //从下一个区间开始数的第n个字符
			cnt *= 10;
			start *= 10;
			++digit;
		}
		//2、具体是哪一个数
		string Str = to_string(start + (n - 1)/digit);
		return Str[(n - 1)%digit] - '0';  //确定是哪一位并转成数字
	}
};