题目描述
blablabla
样例
blablabla
算法1
以第15位数字2为例(2隶属与12,两位数,位于12从左侧以0号开始下标为1的位置)
步骤1:首先确定该数字是属于几位数的;
如果是一位数,n<9;如果是两位数,n<9+90X2=189;
说明是两位数。
因为是从0开始数数。0-9可以表示10个数字,从0开始数可以表示到9。10-99一共有90X2个数字,所以数到两位数能够数到9+90X2=189。
步骤2:确定该数字属于哪个数。10+(15-10)/2= 12。
步骤3:确定是该数中哪一位。15-10-(12-10)*2 = 1, 所以位于“12”的下标为1的位置,即数字2。
以第1001位数字7为例
步骤1:首先确定该数字是属于几位数的;
如果是一位数,n<9;如果是两位数,n<9+90X2=189;如果是三位数,n<189+900X3=2889;
说明是三位数。
步骤2:确定该数字属于哪个数。100+(1001-190)/3= 370。
步骤3:确定是该数中哪一位。1001-190-(370-100)X3 = 1,所以位于“370”的下标为1的位置,即数字1。
blablabla
时间复杂度分析:blablabla
java 代码
public int digitAtIndex(int n) {
if (n<9)
return n;
long num=getRange(n);//确定该数字是属于几位数的
long c=9;
long count=1;
for (int i = 1; i <num ; i++) {
count+=i*c;
c*=10;
}
//确定该数字属于哪个数
long w=(int)Math.pow(10,num-1)+(n-count)/num;
//确定是该数中哪一位
long x=n-count-(w-(int)Math.pow(10,num-1))*num;
String s=String.valueOf(w);
return Integer.parseInt(String.valueOf(s.charAt((int)x)));
}
private static long getRange(int n){
long count=1;
long num=1;
long c=9;
while (count<n){
count= num*c+count;
num++;
c*=10;
}
return num-1;
}
如果n == 10,那个函数返回的是1, 但是10是2位数
所以函数的循环判断条件那里应该改成count<=n
后面几步可以替换成这样
//确定是该数中哪一位
long x = (n - count) % num;
int val;
//倒着算出答案
for (int i = num; i > x; i–)
{
val = w % 10;
w /= 10;
}
return val;
步骤2和步骤3能否说的再详细一些?意思明白了,公式不太懂。。