前言
简单题，但是采用hardcode方式暴力通过
正文
问题来源
本问题来自leetcode上的400题。
问题描述
在无限的整数序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, …中找到第 n 个数字。
注意:
n 是正数且在32为整形范围内 ( n < 2^31)。
示例 1:
输入:
3
输出:
3
示例 2:
输入:
11
输出:
0
说明:
第11个数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ... 里是0，它是10的一部分。
分析：
我的思路是，首先求出那个数，然后根据第几次出现（譬如10th,11th都对应10，10th情况是第一次出现，对应应输出最高位1；11th对应第二位，输出第二位也就是最后一位0）输出对应的位。
自己手撸的C代码,相当不优雅
int findNthDigit(int n) {
//分别是9 9+90*2 9+90*2+900*3 9+90*2+900*3+9000*4 ...
int a[8] = {9,189,2889,38889,488889,5888889,68888889,788888889};
int b[8] = {9,99,999,9999,99999,999999,9999999,99999999};
int i,j;
int sum;
int mod;
for(i=0;i<8;i++)//判断有几位数字 i+1 为有几位
{
if(n<=a[i]) break;
}
if(i==0) return n;//一位就直接返回就好了
sum = b[i-1] + (n-a[i-1]+i)/(i+1);//算出那个数
mod = (n-a[i-1]+i)%(i+1);//算出第几（0代表第一次，i代表第i+1次出现）次出现，
j = i - mod;//除几次可以将所要的位放在个位上
for(i=0;i<j;i++)
{
sum = sum/10;
}
return sum%10;
}
别人写的，思想是一样的。稍微优雅点
char temp[128];
int getDigit(long n, long dIndex) // leftmost number's dIndex == 0
{
sprintf(temp, "%ld", n);
return (int)(temp[dIndex] - '0');
}
int findNthDigit(int n) {
long acc = 0;
long accInc = 1;
long k = 1;
long next = 0;
while (acc + 9 * k * accInc <= n)
{
acc += 9 * k++ * accInc;
next = accInc * 10 - 1;
accInc *= 10;
}
return acc == n ? next % 10 : getDigit(next + (long)ceil((n - acc) / (float)k), (n - acc - 1) % k);//其实不用这样判断(n - acc - 1) % k改为(n - acc + k - 1) % k就不用判断acc是否和n相等了
}
总结：
Be graceful。
结语
为了科学。
