这是悦乐书的第215次更新，第228篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第83题（顺位题号是400）。找到无限整数序列的第n个数字1,2,3,4,5,6,7,8,9,10,11 ……例如：
输入：3
输出：3
输入：11
输出：0
说明：序列1,2,3,4,5,6,7,8,9,10,11 ……的第11位是0，它是数字10的一部分。
注意：n为正整数且符合32位有符号整数（n <2^31）的范围。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
直接使用for循环，从1开始累加字符串，返回第n-1个字符所表示的整数即可。但是此方法严重超时，不建议使用。
public int findNthDigit(int n) {
String str = "";
for (int i=1; i<= n; i++) {
str += i;
}
return Integer.parseInt(str.charAt(n-1)+"");
}
03 第二种解法
题目的意思是有一个以正整数（1,2,3,4，依次向后加1）为基础组成的序列（也可以理解为字符串），传入一个整数n，找出在该序列中的第n位数字。该序列含有以下规律：
-
1-9，有9个一位数，当n小于等于9的时候，可以在里面找到值。
-
10-99，有90个两位数，当n大于9且小于等于180+9=189时，可以在里面找到值。
-
100-999，有900个三位数，当n大于189且小于900×3+189=2889时，可以在里面找到值。
我们可以将此问题分解为三个步骤：
-
先计算该数字的位数，确定范围。
-
找出该数字。
-
确定是该数字中的第几位数。
例如：303
第一步，因为189<303<2889，所以我们要找的是一个三位数，303-189=114，此时n变成114。
第二步，我们要找的数变成了三位数中的第114位，那我们就可以计算出三位数中的第114位数是100+(114-1)/3=137。这里减1是因为在字符串中，索引是从0开始的，而我们的序列字符串是从1开始，所以要减1，你也可以从一开始就减1。
第三步，计算是137中的第几位数，(114-1)%3=2，也就是137的第2位（从0开始）数7，就是我们想要的结果。
在代码中我们使用long类型，预防溢出的风险。
public int findNthDigit2(int n) {
long start = 1, count = 1, num = 9;
while (n > num*count) {
n -= num*count;
count += 1;
start *= 10;
num *= 10;
}
start += (n-1)/count;
String result = start+"";
long index = (n-1)%count;
return result.charAt((int)index)-'0';
}
04 小结
算法专题目前已连续日更超过两个月，算法题文章83+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
