剑指offer-69、数字序列中某⼀位的数字

题⽬形貌

数字以 0123456789101112131415... 的格式作为⼀个字符序列，在这个序列中第 2 位（从下标 0 开始盘算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。
示例1
输⼊：0
返回值：0
示例2
输⼊：2
返回值：2
示例3
输⼊：13
返回值：1
思绪及解答

暴力法

通过渐渐构造数字序列来找到第n位数字

1. public class Solution {
2.     public int findNthDigit(int n) {
3.         if (n < 0) return -1;
4.         if (n == 0) return 0; // 示例1特殊情况处理[2](@ref)
5.         
6.         StringBuilder sequence = new StringBuilder();
7.         int num = 0;
8.         
9.         // 逐步构建序列，直到长度超过n
10.         while (sequence.length() <= n) {
11.             sequence.append(num);
12.             num++;
13.         }
14.         
15.         // 返回第n位字符对应的数字值
16.         return sequence.charAt(n) - '0';
17.     }
18. }

复制代码

• 时间复杂度：O(log₁₀n)，循环次数与n的位数成正比
  
• 空间复杂度：O(1)，只使用常数级别变量
  

添0补齐

假设全部数字都是i位数，通过给较短数字前面添0，使全部数字位数雷同，简化定位逻辑

1. public class Solution {
2.     public int findNthDigit(int n) {
3.         if (n < 0) return -1;
4.         if (n == 0) return 0;
5.         
6.         int digit = 1;              // 数字位数（1位、2位、3位...）
7.         long start = 1;             // 当前位数范围的起始数字
8.         long count = 9;             // 当前位数范围内的数字总位数
9.         
10.         // 步骤1：确定n所在的数字位数
11.         while (n > count) {
12.             n -= count;             // 减去前一个位数范围的数字总位数
13.             digit++;                // 位数增加
14.             start *= 10;            // 起始数字扩大10倍
15.             count = 9L * digit * start; // 计算新的位数范围内的总位数
16.         }
17.         
18.         // 步骤2：确定n所在的具体数字
19.         long num = start + (n - 1) / digit; // 计算目标数字
20.         
21.         // 步骤3：确定n在数字中的具体位置并返回
22.         return Long.toString(num).charAt((n - 1) % digit) - '0';
23.     }
24. }

复制代码

• 时间复杂度：O(log₁₀n)，与数学规律法雷同
  
• 空间复杂度：O(1)，常数空间复杂度
  

免责声明：如果侵犯了您的权益，请联系站长及时删除侵权内容，谢谢合作！qidao123.com:ToB企服之家，中国第一个企服评测及软件市场,开放入驻,技术点评得现金.