剑指 Offer 44数字序列中某一位的数字——LeetCode-Book 三步数学定位法全解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇围绕 LeetCode-Book 仓库中 剑指 Offer 44. 数字序列中某一位的数字 题解文档展开系统讲解如何在序列12345678910111213141516...中通过纯数学方法 O(log n) 定位第 n 个数位。读完后你将掌握“数位数量公式推导 三步定位”的完整解法并能对照仓库中 Python / Java / C 三种语言的实现代码 sfo_44_nth_digit_s1.py 自行验证运行。一、问题定义与核心名词题目要求数字序列为1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...将其所有数位首尾相连组成一个无限长的数字序列12345678910111213141516...给定一个正整数n返回该序列中第n位上的数字。题解文档在展开推导前先做了一组非常关键的“名词约定”这是避免后续推导混乱的基础将 $101112\cdots$ 中的每一位称为数位记为 $n$将 $10, 11, 12, \cdots$ 称为数字记为 $num$数字10是一个两位数称此数字的位数为2记为 $digit$每 $digit$ 位数的起始数字即$1, 10, 100, \cdots$记为 $start$。理解上“数字”是一个完整的整数如123而“数位”是这个整数展开后其中的某一位如123中的2。题目求的是第 $n$ 个“数位”而它归属于某个“数字” $num$。二、数位数量公式count 9 × start × digit按位数对序列分段观察位数 digit该段数字范围数字个数每个数字贡献的数位该段数位数量 count11 ~ 991$9 \times 1 \times 1 9$210 ~ 99902$9 \times 10 \times 2 180$3100 ~ 9999003$9 \times 100 \times 3 2700$41000 ~ 999990004$9 \times 1000 \times 4 36000$规律很清晰$digit$ 位数的数字一共有 $9 \times start$ 个例如三位数是 100 到 999恰好 $9 \times 100$ 个每个数字贡献 $digit$ 个数位因此各 $digit$ 下的数位数量 $count$ 满足$$ count 9 \times start \times digit $$有了这个公式整个求解过程就可以拆成三步确定 $n$ 所在数字的位数记为 $digit$确定 $n$ 所在的数字记为 $num$确定 $n$ 是 $num$ 中的哪一数位并返回结果。三、第一步确定所在数字的位数 digit核心思路循环让 $n$ 依次减去一位数、两位数、…… 的数位数量 $count$直至 $n \leq count$ 时跳出循环。由于 $n$ 已经减去了一位数、两位数、……、$(digit-1)$ 位数的数位数量 $count$所以跳出循环时的 $n$ 已经变成了“从起始数字 $start$ 开始计数”的相对位置。Python 实现digit, start, count 1, 1, 9 while n count: n - count start * 10 # 1, 10, 100, ... digit 1 # 1, 2, 3, ... count 9 * start * digit # 9, 180, 2700, ...Java 实现int digit 1; long start 1; long count 9; while (n count) { n - count; start * 10; // 1, 10, 100, ... digit 1; // 1, 2, 3, ... count digit * start * 9; // 9, 180, 2700, ... }C 实现int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; // 1, 10, 100, ... digit 1; // 1, 2, 3, ... count digit * start * 9; // 9, 180, 2700, ... }结论所求数位 ① 位于某个 $digit$ 位数中② 是从数字 $start$ 开始计数的第 $n$ 个数位。从源码结构看Java 与 C 版本刻意将start、count、num声明为long见 sfo_44_nth_digit_s1.java 第 16-17 行而digit保持int。这样做的意义在于start会持续乘以 101 → 10 → 100 → …count digit * start * 9在高位数区间的增长很快用 64 位整数可以完全避免溢出而 Python 整数本身无溢出问题因此 Python 版本 不需要额外声明类型。四、第二步确定所在数字 num跳出循环后$n$ 是从 $start$ 起、以“数位”为单位计数的偏移量。而每个 $digit$ 位数字占据 $digit$ 个数位因此第 $n$ 个数位落在从 $start$ 开始的第 $[(n - 1) / digit]$ 个数字中注意 $start$ 本身算第 0 个数字Pythonnum start (n - 1) // digitJavalong num start (n - 1) / digit;Clong num start (n - 1) / digit;结论所求数位在数字 $num$ 中。这里(n - 1)是典型的“转 0 基”处理循环结束时 $n$ 是 1 基偏移最小为 1减 1 后整除 $digit$ 才能对齐到“第几个数字”。五、第三步确定 num 中的具体数位确定了 $num$ 之后所求数位就是 $num$ 的第 $(n - 1) % digit$ 位数字的首个数位记为第 0 位。三种语言统一采用“转字符串后取下标”的做法Pythons str(num) # 转化为 string res int(s[(n - 1) % digit]) # 获得 num 的 第 (n - 1) % digit 个数位并转化为 intJavaString s Long.toString(num); // 转化为 string int res s.charAt((n - 1) % digit) - 0; // 获得 num 的 第 (n - 1) % digit 个数位并转化为 intCstring s to_string(num); // 转化为 string int res s[(n - 1) % digit] - 0; // 获得 num 的 第 (n - 1) % digit 个数位并转化为 int结论所求数位就是 $res$。六、完整代码与仓库实现题目文档给出的完整解法与仓库中三个语言的落盘实现完全一致可直接复制运行Pythonsfo_44_nth_digit_s1.py 第 11-20 行class Solution: def findNthDigit(self, n: int) - int: digit, start, count 1, 1, 9 while n count: # 1. n - count start * 10 digit 1 count 9 * start * digit num start (n - 1) // digit # 2. return int(str(num)[(n - 1) % digit]) # 3.Javasfo_44_nth_digit_s1.java 第 13-27 行class Solution { public int findNthDigit(int n) { int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; digit 1; count digit * start * 9; } long num start (n - 1) / digit; // 2. return Long.toString(num).charAt((n - 1) % digit) - 0; // 3. } }Csfo_44_nth_digit_s1.cpp 第 10-25 行class Solution { public: int findNthDigit(int n) { int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; digit 1; count digit * start * 9; } long num start (n - 1) / digit; // 2. return to_string(num)[(n - 1) % digit] - 0; // 3. } };三个语言的驱动代码均以n 3作为默认测试用例如 Python 驱动 第 24-28 行预期输出为3对应序列开头的1, 2, 3。仓库各语言目录下的公共头文件位于 codes/cpp/include/、codes/java/include/、codes/python/include/主要为链表与二叉树题型提供公共节点定义本题解并不依赖它们直接编译运行即可。七、运行过程推演以两个典型输入手工推演验证每一步的状态变化例 1n 11第 11 个数位序列为...8, 9, 1, 0, ...答案应为0初始digit1, start1, count9。n11 9进入循环n 11 - 9 2start 10digit 2count 180n 2 ≤ 180跳出循环。此时含义是第 11 个数位位于两位数区间是从10开始的第 2 个数位num 10 (2 - 1) // 2 10下标(2 - 1) % 2 1取str(10)[1]即0。例 2n 19答案应为4因为两位区间的排布是10,11,12,13,14第一轮后n 19 - 9 10start10, digit2, count180跳出循环num 10 (10 - 1) // 2 14下标(10 - 1) % 2 1取str(14)[1]即4。这两个例子也体现了两步公式的分工整除(n-1) // digit负责“跳到哪个数字”取模(n-1) % digit负责“在数字内取哪一位”。八、复杂度分析时间复杂度 $O(\log n)$所求数位 $n$ 对应数字 $num$ 的位数 $digit$ 最大为 $O(\log n)$第一步最多循环 $O(\log n)$ 次第三步中将 $num$ 转化为字符串使用 $O(\log n)$ 时间因此总体为 $O(\log n)$。空间复杂度 $O(\log n)$将数字 $num$ 转化为字符串str(num)占用 $O(\log n)$ 的额外空间。对题目常见的取值范围n为 32 位正整数而言循环实际上最多执行 9~10 次十位数的数位总量9 × 10^9 × 10 9 × 10^10已远超2^31 - 1因此 while 循环必然在digit达到 10 之前结束这也解释了为什么只需在 Java/C 中将start、count声明为long而无需担心溢出或死循环。九、总结剑指 Offer 44 的精髓在于把“无限序列中的定位问题”转化为三段封闭的数学计算先用 $count 9 \times start \times digit$ 逐段排除确定位数再用整除和取模分别锁定数字与数位。仓库中的三份实现Python、Java、C逻辑完全同构差异仅在类型声明与字符串 API适合作为数学思维类题目的模板。同样的“按位数分段计数”思想在 剑指 Offer 43. 1n 整数中 1 出现的次数 中也有应用可结合阅读。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 剑指 Offer 44：数字序列中某一位的数字——LeetCode-Book 三步数学定位法全解
剑指 Offer 44数字序列中某一位的数字——LeetCode-Book 三步数学定位法全解【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book本篇围绕 LeetCode-Book 仓库中 剑指 Offer 44. 数字序列中某一位的数字 题解文档展开系统讲解如何在序列12345678910111213141516...中通过纯数学方法 O(log n) 定位第 n 个数位。读完后你将掌握“数位数量公式推导 三步定位”的完整解法并能对照仓库中 Python / Java / C 三种语言的实现代码 sfo_44_nth_digit_s1.py 自行验证运行。一、问题定义与核心名词题目要求数字序列为1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, ...将其所有数位首尾相连组成一个无限长的数字序列12345678910111213141516...给定一个正整数n返回该序列中第n位上的数字。题解文档在展开推导前先做了一组非常关键的“名词约定”这是避免后续推导混乱的基础将 $101112\cdots$ 中的每一位称为数位记为 $n$将 $10, 11, 12, \cdots$ 称为数字记为 $num$数字10是一个两位数称此数字的位数为2记为 $digit$每 $digit$ 位数的起始数字即$1, 10, 100, \cdots$记为 $start$。理解上“数字”是一个完整的整数如123而“数位”是这个整数展开后其中的某一位如123中的2。题目求的是第 $n$ 个“数位”而它归属于某个“数字” $num$。二、数位数量公式count 9 × start × digit按位数对序列分段观察位数 digit该段数字范围数字个数每个数字贡献的数位该段数位数量 count11 ~ 991$9 \times 1 \times 1 9$210 ~ 99902$9 \times 10 \times 2 180$3100 ~ 9999003$9 \times 100 \times 3 2700$41000 ~ 999990004$9 \times 1000 \times 4 36000$规律很清晰$digit$ 位数的数字一共有 $9 \times start$ 个例如三位数是 100 到 999恰好 $9 \times 100$ 个每个数字贡献 $digit$ 个数位因此各 $digit$ 下的数位数量 $count$ 满足$$ count 9 \times start \times digit $$有了这个公式整个求解过程就可以拆成三步确定 $n$ 所在数字的位数记为 $digit$确定 $n$ 所在的数字记为 $num$确定 $n$ 是 $num$ 中的哪一数位并返回结果。三、第一步确定所在数字的位数 digit核心思路循环让 $n$ 依次减去一位数、两位数、…… 的数位数量 $count$直至 $n \leq count$ 时跳出循环。由于 $n$ 已经减去了一位数、两位数、……、$(digit-1)$ 位数的数位数量 $count$所以跳出循环时的 $n$ 已经变成了“从起始数字 $start$ 开始计数”的相对位置。Python 实现digit, start, count 1, 1, 9 while n count: n - count start * 10 # 1, 10, 100, ... digit 1 # 1, 2, 3, ... count 9 * start * digit # 9, 180, 2700, ...Java 实现int digit 1; long start 1; long count 9; while (n count) { n - count; start * 10; // 1, 10, 100, ... digit 1; // 1, 2, 3, ... count digit * start * 9; // 9, 180, 2700, ... }C 实现int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; // 1, 10, 100, ... digit 1; // 1, 2, 3, ... count digit * start * 9; // 9, 180, 2700, ... }结论所求数位 ① 位于某个 $digit$ 位数中② 是从数字 $start$ 开始计数的第 $n$ 个数位。从源码结构看Java 与 C 版本刻意将start、count、num声明为long见 sfo_44_nth_digit_s1.java 第 16-17 行而digit保持int。这样做的意义在于start会持续乘以 101 → 10 → 100 → …count digit * start * 9在高位数区间的增长很快用 64 位整数可以完全避免溢出而 Python 整数本身无溢出问题因此 Python 版本 不需要额外声明类型。四、第二步确定所在数字 num跳出循环后$n$ 是从 $start$ 起、以“数位”为单位计数的偏移量。而每个 $digit$ 位数字占据 $digit$ 个数位因此第 $n$ 个数位落在从 $start$ 开始的第 $[(n - 1) / digit]$ 个数字中注意 $start$ 本身算第 0 个数字Pythonnum start (n - 1) // digitJavalong num start (n - 1) / digit;Clong num start (n - 1) / digit;结论所求数位在数字 $num$ 中。这里(n - 1)是典型的“转 0 基”处理循环结束时 $n$ 是 1 基偏移最小为 1减 1 后整除 $digit$ 才能对齐到“第几个数字”。五、第三步确定 num 中的具体数位确定了 $num$ 之后所求数位就是 $num$ 的第 $(n - 1) % digit$ 位数字的首个数位记为第 0 位。三种语言统一采用“转字符串后取下标”的做法Pythons str(num) # 转化为 string res int(s[(n - 1) % digit]) # 获得 num 的 第 (n - 1) % digit 个数位并转化为 intJavaString s Long.toString(num); // 转化为 string int res s.charAt((n - 1) % digit) - 0; // 获得 num 的 第 (n - 1) % digit 个数位并转化为 intCstring s to_string(num); // 转化为 string int res s[(n - 1) % digit] - 0; // 获得 num 的 第 (n - 1) % digit 个数位并转化为 int结论所求数位就是 $res$。六、完整代码与仓库实现题目文档给出的完整解法与仓库中三个语言的落盘实现完全一致可直接复制运行Pythonsfo_44_nth_digit_s1.py 第 11-20 行class Solution: def findNthDigit(self, n: int) - int: digit, start, count 1, 1, 9 while n count: # 1. n - count start * 10 digit 1 count 9 * start * digit num start (n - 1) // digit # 2. return int(str(num)[(n - 1) % digit]) # 3.Javasfo_44_nth_digit_s1.java 第 13-27 行class Solution { public int findNthDigit(int n) { int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; digit 1; count digit * start * 9; } long num start (n - 1) / digit; // 2. return Long.toString(num).charAt((n - 1) % digit) - 0; // 3. } }Csfo_44_nth_digit_s1.cpp 第 10-25 行class Solution { public: int findNthDigit(int n) { int digit 1; long start 1; long count 9; while (n count) { // 1. n - count; start * 10; digit 1; count digit * start * 9; } long num start (n - 1) / digit; // 2. return to_string(num)[(n - 1) % digit] - 0; // 3. } };三个语言的驱动代码均以n 3作为默认测试用例如 Python 驱动 第 24-28 行预期输出为3对应序列开头的1, 2, 3。仓库各语言目录下的公共头文件位于 codes/cpp/include/、codes/java/include/、codes/python/include/主要为链表与二叉树题型提供公共节点定义本题解并不依赖它们直接编译运行即可。七、运行过程推演以两个典型输入手工推演验证每一步的状态变化例 1n 11第 11 个数位序列为...8, 9, 1, 0, ...答案应为0初始digit1, start1, count9。n11 9进入循环n 11 - 9 2start 10digit 2count 180n 2 ≤ 180跳出循环。此时含义是第 11 个数位位于两位数区间是从10开始的第 2 个数位num 10 (2 - 1) // 2 10下标(2 - 1) % 2 1取str(10)[1]即0。例 2n 19答案应为4因为两位区间的排布是10,11,12,13,14第一轮后n 19 - 9 10start10, digit2, count180跳出循环num 10 (10 - 1) // 2 14下标(10 - 1) % 2 1取str(14)[1]即4。这两个例子也体现了两步公式的分工整除(n-1) // digit负责“跳到哪个数字”取模(n-1) % digit负责“在数字内取哪一位”。八、复杂度分析时间复杂度 $O(\log n)$所求数位 $n$ 对应数字 $num$ 的位数 $digit$ 最大为 $O(\log n)$第一步最多循环 $O(\log n)$ 次第三步中将 $num$ 转化为字符串使用 $O(\log n)$ 时间因此总体为 $O(\log n)$。空间复杂度 $O(\log n)$将数字 $num$ 转化为字符串str(num)占用 $O(\log n)$ 的额外空间。对题目常见的取值范围n为 32 位正整数而言循环实际上最多执行 9~10 次十位数的数位总量9 × 10^9 × 10 9 × 10^10已远超2^31 - 1因此 while 循环必然在digit达到 10 之前结束这也解释了为什么只需在 Java/C 中将start、count声明为long而无需担心溢出或死循环。九、总结剑指 Offer 44 的精髓在于把“无限序列中的定位问题”转化为三段封闭的数学计算先用 $count 9 \times start \times digit$ 逐段排除确定位数再用整除和取模分别锁定数字与数位。仓库中的三份实现Python、Java、C逻辑完全同构差异仅在类型声明与字符串 API适合作为数学思维类题目的模板。同样的“按位数分段计数”思想在 剑指 Offer 43. 1n 整数中 1 出现的次数 中也有应用可结合阅读。【免费下载链接】LeetCode-Book《剑指 Offer》《图解算法数据结构》《Krahets 笔面试精选 88 题》Python, Java, C 解题代码项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Book创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考