剑指offer-69、数字序列中某⼀位的数字
题⽬描述数字以 0123456789101112131415... 的格式作为⼀个字符序列，在这个序列中第 2 位（从下标 0 开始计算）是 2 ，第 10 位是 1 ，第 13 位是 1 ，以此类题，请你输出第 n 位对应的数字。
示例1
输⼊：0
返回值：0
示例2
输⼊：2
返回值：2
示例3
输⼊：13
返回值：1
思路及解答
暴力法
通过逐步构造数字序列来找到第n位数字
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';
}
}
[*]时间复杂度：O(log₁₀n)，循环次数与n的位数成正比
[*]空间复杂度：O(1)，只使用常数级别变量
添0补齐
假设所有数字都是i位数，通过给较短数字前面添0，使所有数字位数相同，简化定位逻辑
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';
}
}
[*]时间复杂度：O(log₁₀n)，与数学规律法相同
[*]空间复杂度：O(1)，常数空间复杂度
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！ 前排留名，哈哈哈 感谢分享，下载保存了，貌似很强大 喜欢鼓捣这些软件，现在用得少，谢谢分享！ 分享、互助 让互联网精神温暖你我 yyds。多谢分享 分享、互助 让互联网精神温暖你我 感谢分享，下载保存了，貌似很强大 热心回复！ 鼓励转贴优秀软件安全工具和文档！ 感谢分享，学习下。 东西不错很实用谢谢分享 热心回复！ 不错，里面软件多更新就更好了 用心讨论，共获提升！ 懂技术并乐意极积无私分享的人越来越少。珍惜 不错，里面软件多更新就更好了 过来提前占个楼 感谢，下载保存了 这个有用。
页:
[1]
2