机械设备上海网站建设,泰州做网站软件,wordpress标签别名,小程序后端开发教程文章目录题目思路代码复杂度分析致谢题目
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中#xff0c;第5位#xff08;从下标0开始计数#xff09;是5#xff0c;第13位是1#xff0c;第19位是4#xff0c;等等。
请写一个函数#xff0c…
文章目录题目思路代码复杂度分析致谢题目
数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中第5位从下标0开始计数是5第13位是1第19位是4等等。
请写一个函数求任意第n位对应的数字。 思路
我们注意到如果
将 01234567891⋯ 中的每一位称为 位 记为 n 将 10,11,12,⋯ 称为 数字 记为 num 数字 10 是一个两位数称此数字的 位数 为 2 记为 digit 每 digit 位数的起始数字即1,10,100,⋯记为 start 。个位数共有 1 ~ 9 九个数字称个位数的 数字数量 为 9 记为 num_count 。十位数共有 10~99 90个数字每个数字有两位共占序列化 90*2180 位称十位数的 数位数量 为 180 记为 count 。
可以得到下表个位数不计入0
数字范围位数数字数量共占序列化多少位1~919910~99290180100~99939002700……………………start~enddigit9*start9 * start * digit
可以得到三个公式
位数递推公式 digit digit 1起始数字递推公式 start start * 10数字数量计算公式 num_count 9 * start数位数量计算公式 count 9 * start * digit
我们可以将求 第n位对应的数字 求解过程分为以下几步
确定 n 所在 数字 的 位数digit 确定 n 所在的 数字num 确定 n 是 num 中的哪一位。
第一步
在几位数的范围内
while(ncount){n - count;start * 10;digit;count 9*start*digit;
}第二步
是哪个数字
int num start(n-1)/digit;为什么是 (n-1)/digit 而不是 n/digit
首先看一张图
以两位数为例当执行完 nn-9 之后n 与各个两位数数位的对应关系如上图所示。以13为例当我们知道 n713中的1 时由 n/23 可得 n 是十位数起始数字之后的第三个但是当 n813中的3 时由 n/24 得到 n 对应的是十位数起始数字之后的第四个这是错误的十位数起始数字之后的第四个是 14 而非 13 因此计算时需要将 n 进行 减一操作因为我们将起始数字看作 第0个数 而非 第1个数 。
为什么是 (n-1)/digit 而不是 n/digit-1
仍然以两位数为例当 n 对应非起始数字时两种算法是没有区别的但是当 n 对应起始数字时不论 n0 or n1 (n-1)/digit 的计算结果都为 0 而 n/digit-1 的计算结果都为 -1 。 (n-1)/digit 对应的数字 num start 0 10 正确而 n/digit-1 对应的数字 num start (-1) 9 变成了个位数错误。
总而言之对 n 进行 减一操作 是因为 起始数字应视为 start 0虽然它是两位数里面的 第一个 数字但是我们在公式里说的 第几个 是 该数字相对于起始数字 而言的因此要统统减一。而之所以不是 先除再减 而是 先减再除 是因为 要考虑逻辑顺序对起始数字的影响 。
第三步
处于对应数字的哪一位
num s[(n-1)%digit] - 0;(n-1)%digit 计算的便是对应的 数位 n减一的原因和第二步中相同不再赘述。 代码
class Solution {
public:int findNthDigit(int n) {long long start1, count9, digit1;while(ncount){n - count;start * 10;digit;count 9*start*digit;}int num start(n-1)/digit;//所在数字string s to_string(num);num s[(n-1)%digit] - 0;//处于所在num的哪一位return num;}
};复杂度分析
时间复杂度 O(logn) 所求数位 n 对应数字 num 的位数 digit 最大为 O(log n) 第一步最多循环 O(log n) 次第三步中将 num 转化为字符串使用 O(log n) 时间因此总体为 O(log n) 。
空间复杂度 O(logn) 将数字 num 转化为字符串 str(num) 占用 O(logn) 的额外空间。 致谢
思路中的部分想法、复杂度分析源于K神的题解鞠躬致谢。
