剑指offer-69、数字序列中某⼀位的数字
<h2 id="题描述">题⽬描述</h2><p>数字以 0123456789101112131415... 的格式作为⼀个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。</p>
<p>示例1</p>
<p>输⼊：0<br>
返回值：0</p>
<p>示例2<br>
输⼊：2<br>
返回值：2</p>
<p>示例3<br>
输⼊：13<br>
返回值：1</p>
<h2 id="思路及解答">思路及解答</h2>
<h3 id="暴力法">暴力法</h3>
<p>通过逐步构造数字序列来找到第n位数字</p>
<pre><code class="language-java">public class Solution {
public int findNthDigit(int n) {
if (n < 0) return -1;
if (n == 0) return 0; // 示例1特殊情况处理(@ref)
StringBuilder sequence = new StringBuilder();
int num = 0;
// 逐步构建序列，直到长度超过n
while (sequence.length() <= n) {
sequence.append(num);
num++;
}
// 返回第n位字符对应的数字值
return sequence.charAt(n) - '0';
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(n)，需要构造长度至少为n的字符串</li>
<li><strong>空间复杂度</strong>：O(n)，需要存储构造的字符串序列</li>
</ul>
<h3 id="数学规律">数学规律</h3>
<p>利用数字位数分布的数学规律，直接定位第n位所在的数字和具体位置</p>
<p><strong>数字位数分布规律：</strong></p>
<ul>
<li><strong>1位数</strong>：0-9 → 10个数字 × 1位 = 10位</li>
<li><strong>2位数</strong>：10-99 → 90个数字 × 2位 = 180位</li>
<li><strong>3位数</strong>：100-999 → 900个数字 × 3位 = 2700位</li>
<li><strong>k位数</strong>：9×10ᵏ⁻¹个数字 × k位</li>
</ul>
<pre><code class="language-java">public class Solution {
public int findNthDigit(int n) {
if (n < 0) return -1;
if (n == 0) return 0;
int digit = 1; // 数字位数（1位、2位、3位...）
long start = 1; // 当前位数范围的起始数字
long count = 9; // 当前位数范围内的数字总位数
// 步骤1：确定n所在的数字位数
while (n > count) {
n -= count; // 减去前一个位数范围的数字总位数
digit++; // 位数增加
start *= 10; // 起始数字扩大10倍
count = 9L * digit * start; // 计算新的位数范围内的总位数
}
// 步骤2：确定n所在的具体数字
long num = start + (n - 1) / digit; // 计算目标数字
// 步骤3：确定n在数字中的具体位置并返回
return Long.toString(num).charAt((n - 1) % digit) - '0';
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log₁₀n)，循环次数与n的位数成正比</li>
<li><strong>空间复杂度</strong>：O(1)，只使用常数级别变量</li>
</ul>
<h3 id="添0补齐">添0补齐</h3>
<p>假设所有数字都是i位数，通过给较短数字前面添0，使所有数字位数相同，简化定位逻辑</p>
<pre><code class="language-java">public class Solution {
public int findNthDigit(int n) {
if (n < 0) return -1;
if (n == 0) return 0;
int i = 1; // 数字位数
// 通过添0补齐，使所有数字都视为i位数
while (i * Math.pow(10, i) < n) {
n += Math.pow(10, i); // 添0增加的位数
i++;
}
// 定位目标数字和具体位置
String num = String.valueOf(n / i);
return num.charAt(n % i) - '0';
}
}
</code></pre>
<ul>
<li><strong>时间复杂度</strong>：O(log₁₀n)，与数学规律法相同</li>
<li><strong>空间复杂度</strong>：O(1)，常数空间复杂度</li>
</ul>
</div>
<div id="MySignature" role="contentinfo">
<p>本文来自在线网站：seven的菜鸟成长之路，作者：seven，转载请注明原文链接：www.seven97.top</p><br><br>
来源：https://www.cnblogs.com/sevencoding/p/19526096
頁:
[1]