题目描述
blablabla
样例
class Solution {
public:
int digitAtIndex(int n) {
long long i = 1, s = 9, base = 1;//i表示是几位数,s表示位数共有多少个,base表示位数的起始值。
while(n > i * s) { // 9, 90, 900, 9000, 90000, i * s表示位数总共占多少位。
n -= i * s; // 1000 - 9 - 90 * 2 - 900 * 3 ,当i= 3 时不符合条件,说明是在三位数里面。
i ++;
s *= 10;
base *= 10;
}
int number = base + (n + i - 1) / i - 1; //求位数的第几个数, 1000 - 9 - 180 = n , n / 3 + base - 1(考虑0故减1), 向上取整 n + i - 1。
int r = n % i ? n % i : i; // 除不尽就是第几位,除尽力了就是最后一位。
for (int j = 0; j < i - r; j ++) number /= 10; //求数的第i - r位,取出第i - r位。
return number % 10;
}
};
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度分析:blablabla
C++ 代码
blablabla
这一行写的有点冗余
int number = base + (n + i - 1) / i - 1;
其实等价于
int number = base + (n - 1) / i ;
其实s也可以省略hhhh
式中 number = base + (n + i - 1) / i - 1 ; 引入向上取整函数后为 number = base + ceil( n * 1.0 / i);
为什么会报错???求解啊啊啊啊
奥奥懂了 没减 1 哈哈
应该是 number = base + ceil( n * 1.0 / i) - 1;
### 感谢分享
牛逼!!!
1位数从0-9,不是10个吗?为什么第一个S = 9?
先无视掉了 0
按照算法分析我们是从第一位开始计数的,那么0123456789中的9是第十位了,但是题目中是从第0位开始计数的,认为9是第九位,所以参数n要转到我们的以第一位开始计数的算法中来,则应该改为n+1,之后一位数共10个数,我们为了统一,故减去0那一个,就成了还是n,但一位数从1-9了
你好,我在试数的过程中有一些问题,如下,当输入n为13时候,第一次试数,1> 13>9//成立 n>is=9
n=4 n=n-is=13-9
i=2; 更新:i++
s=90; s=s10=90
base=10; base=base10=10
——————
2> 4>180//成立
n=4-180=-176;
i=3;
s=900;
base=100;
——————
3> 不成立
此时由于在第2>次循环中已经更新了i,s,和base的值;
所以,对于后面的程序执行结果产生了错误的影响。
请问你能帮我解释一下这里的原因吗?
4 > 180 成立??
不好意思,我刚开始用一个较大的数字试数不成功后,改成了一个较小的数字,没注意到这一点。谢谢你。