题目难度: 中等原题链接今天继续更新 Leetcode 的剑指 Offer专项突击版系列, 大家在公众号算法精选里回复剑指offer2就能看到该系列当前连载的所有文章了, 记得关注哦~题目描述某班级学号记录系统发生错乱原整数学号序列 [1,2,3,4,…] 分隔符丢失后变为 1234… 的字符序列。请实现一个函数返回该字符序列中的第 k 位数字。示例 1输入k 5输出5示例 2输入k 12输出1解释第 12 位数字在序列 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, … 里是 1 它是 11 的一部分。提示0 k 2^31题目思考能否找到什么规律?解决方案思路观察序列本身:0~9 只占 1 位, 共 10 个10~99 占 2 位, 共 90 个100~999 占 3 位, 共 900 个1000~9999 占 4 位, 共 9000 个…为了保持一致, 我们可以将 1 位的时候改成从 1 开始, 把 k0 作为特殊情况, 这样 1 位也只有 9 个, 即 1~9这样我们就很容易发现规律, 假设当前位数是 le:每一位的开始值 start 是pow(10, le-1)每一位的数字数目是9*start每一位的字符总数则是9*start*le(因为每个数字有 le 个字符)所以我们可以逐渐增加位数, 统计当前总共的字符个数假设 le 位数下的字符总数是 cnt, le1 下的字符总数是 nextcnt, 那么如果 k 在[cnt, nextcnt)范围内, 那就说明 k 落在的数字一定有 le 位这样一来, 我们只需要定位 k 具体对应到的数字, 以及所在数字的第几位即可而由于每个数字占有 le 位, 所以 k 对应的数字就是start(k-cnt)/le, 而具体 k 是在该数字的第几位, 则是(k-cnt)%le下面的代码对必要步骤有详细的解释, 方便大家理解复杂度时间复杂度O(logN)只需要按位数遍历即可, k 的位数是 logN空间复杂度O(1)只使用了常数个变量代码classSolution:deffindKthNumber(self,k:int)-int:ifk0:return0# 初始化计数值为1, 因为start最开始是1, 此时已经有1个字符了cnt1# 初始化位数为1位le1whilekcnt:# 求当前位数下的startstart10**(le-1)# 求当前位数1情况下的字符总数nexcntcnt9*start*leifknexcnt:# 当前n落在范围内, 找对应的数字和该数字中n对应的位(偏移量)i,offsetdivmod(k-cnt,le)numstarti# 将数字转成字符串, 其偏移量下标对应的位即为所求returnint(str(num)[offset])# 更新字符总数, 同时位数加1, 继续循环cntnexcnt le1大家可以在下面这些地方找到我~我的 GitHub我的 Leetcode我的 CSDN我的知乎专栏我的头条号我的牛客网博客我的公众号: 算法精选, 欢迎大家扫码关注~